Stack

Da Hacknowledge.

Al momento della creazione di ogni processo, il sistema operativo assegna a quest'ultimo un'area di memoria, chiamata stack, nella quale il processo potrà salvare le sue variabili locali, eventuali dati temporanei e chiamate a funzione. L'indirizzo base dello stack, su un sistema Linux, è all'indirizzo di memoria 0xc0000000, e da lì gli indirizzi vanno a decrescere. Lo stack ha inoltre una struttura LIFO (Last in, first out), ovvero l'ultimo dato immesso su di esso è in genere il primo a essere prelevato. Lo possiamo proprio concettualmente vedere come una pila, in cui di volta in volta infilo un nuovo oggetto spostandomi verso l'alto, e il primo oggetto che andrò ad estrarre dall'alto sarà proprio l'ultimo che ho inserito. Ovviamente questo esempio è solo da prendere a livello concettuale, dato che in realtà come abbiamo appena visto gli indirizzi sullo stack non vanno dal basso verso l'alto ma al contrario, partendo dall'indirizzo base 0xc0000000 e andando a decrescere man mano che vengono inseriti nuovi oggetti, ma questo non modifica molto l'esempio concettuale appena proposto. Al massimo possiamo vedere lo stack come una pila al contrario che 'sfida' le leggi fisiche di gravità.

A livello hardware, e quindi di codice macchina, possiamo gestire lo stack attraverso due registri della CPU:

• ESP - Stack pointer. È il registro che punta all'attuale cima dello stack, ovvero l'indirizzo corrente a cui si trova lo stack dell'applicazione. Supponiamo ad esempio di avere uno stack completamente vuoto e di cominciare dall'indirizzo 0xc0000000 (nella realtà non capiterà mai una situazione del genere, dato che i processi cominciano salvando automaticamente sullo stack informazioni sulle chiamate di funzioni principali). Se salviamo un int a 4 byte sullo stack in questa situazione, la nostra variabile verrà memorizzata, la cima dello stack attuale sarà all'indirizzo 0xc0000000 - 4 = 0xbffffffc, e quindi ESP dopo il salvataggio della variabile conterrà il valore 0xbffffffc. Abbiamo quindi imparato una cosa fondamentale nella gestione dello stack: per scrivere un valore sullo stack basta decrementare ESP di tante unità quanti sono i byte da scrivere sullo stack, quindi scrivere il valore da salvare sull'indirizzo puntato da ESP. Esempio:

subl   $4,%esp     ; Sottraggo 4 byte alla cima dello stack
movl   $1,(%esp)   ; Salvo il valore 0x00000001 sullo stack (4 byte)

L'ISA Intel mette a disposizione una sola istruzione per compiere questa operazione: push. Semplicemente, richiamo l'istruzione push passando come argomento il valore o il registro da salvare sullo stack, e automaticamente decrementa lo stack pointer di tante unità quanti sono i byte da salvare e scrive sul nuovo indirizzo puntato da ESP il valore. La scrittura di sopra si può tranquillamente condensare in un

pushl   $1

Analogalmente, per rimuovere a livello logico un dato dallo stack basta sommare alla cima dello stack tante unità quanti sono i byte che si vogliono rimuovere. Alla scrittura successiva sullo stack, verrà preso l'indirizzo puntato da ESP e i nuovi dati verranno scritti lì, sovrascrivendo quindi i dati precedenti. Possiamo anche salvare l'attuale cima dello stack su un registro e rimuovere dallo stack i dati appena letti in questo modo. Basta copiare il valore puntato da ESP in un registro e sommare ad ESP tante unità quanti sono i byte letti. Tornando all'esempio di prima, possiamo scrivere un int sullo stack e poi andare a leggere la cima dallo stack e salvare il valore lì puntato su un registro in questo modo:

movl   (%esp),%eax   ; Copio l'attuale valore presente in cima allo stack (4 byte) in EAX
addl   $4,%esp       ; Sommo 4 byte alla cima dello stack, dicendo al sistema che quello spazio è ora libero

Anche qui, la ISA Intel mette a disposizione una sola istruzione per effettuare quest'operazione: pop. La sintassi, semplicemente, prevede che alla pop si passi il registro in cui salvare la cima dello stack. Il codice di sopra è perfettamente equivalente ad una

popl   %eax

A livello concettuale quindi le due istruzioni rispettivamente salvano un elemento sulla cima dello stack e prelevano il valore attualmente presente in cima allo stack per salvarlo in un registro.

Attenzione però a ricordare sempre le caratteristiche LIFO dello stack. Se effettuo un salvataggio di dati in quest'ordine

pushl   $1
pushl   $2
pushl   $3

i dati verranno poi prelevati dallo stack in ordine inverso, ovvero prima 3, poi 2, poi 1, in quanto viene sempre prelevato per primo l'ultimo elemento inserito, in quanto rappresenta la cima dello stack. Inoltre, è in genere buona norma, quando i byte scritti sullo stack non servono più, deallocarli, o effettuando tante pop quante sono le push, oppure sommando a ESP tante unità quanti sono i byte scritti, in modo da minimizzare l'occupazione di questa zona di memoria.

• EBP - base pointer. Questo registro contiene l'indirizzo di base dello stack per il processo corrente. Inizialmente, all'avvio del processo viene scritto in EBP il suo indirizzo base dello stack, quindi tale valore viene copiato in ESP. A questo punto EBP rimane in genere non toccato, mentre invece ESP può essere incrementato o decrementato partendo dal valore base ogni volta che vengono salvati o prelevati valori sullo stack.

Ci sono inoltre altre due istruzioni che tornano molto utili quando si devono scrivere righe di codice Assembly da integrare in progetti già esistenti e in modo da ridurne l'impatto: pusha e popa. Queste due istruzioni rispettivamente salvano sullo stack la situazione attuale dei registri, e prelevano la situazione dei registri salvata precedentemente sullo stack ripristinandola. Esempio classico di utilizza:

; Frammento di codice ASM richiamato dall'esterno
 
pusha   ; Salvo sullo stack la situazione attuale dei registri
 
; Codice eseguito dalla procedura
 
popa    ; Ripristino la situazione iniziale dei registri prelevandola dallo stack

Ora possiamo anche capire come vengono gestiti a basso livello gli array nei linguaggi di programmazione ad alto livello. Chi viene dal C saprà che in questo linguaggio un array non è altro che un puntatore tipizzato al primo elemento in esso contenuto. Questa caratteristica rispecchia proprio quello che accade a basso livello: un array non è altro che una lista di elementi dello stesso tipo. Quando un compilatore incontra la definizione di un array, salva tutti i suoi elementi, ovviamente in ordine inverso, sullo stack. Ad ogni elemento inserito sullo stack il registro ESP viene incrementato di tante unità quanti i byte scritti, e complessivamente, se ho un array di n elementi,

ESP = ESP + n*(dimensione singolo elemento)

Quello che interessa a me programmatore di alto livello è sapere a che indirizzo di memoria è salvato l'array, quindi, dopo la fase di inserimento, mi salvo da qualche parte la cima dello stack, che rappresenta l'indirizzo del primo elemento del mio array. Esempio: l'allocazione di un array di questo tipo in C

int v[] = { 0,1,2,3,4 };

viene riscritta in Assembly come

v:      .long   0   ; Variabile che conterrà l'indirizzo del primo elemento del vettore
 
......
 
pushl   $4       ; Salvo gli elementi del vettore sullo stack
pushl   $3
pushl   $2
pushl   $1
pushl   $0
movl    %esp,v   ; Copio l'attuale cima dello stack in v

Ora v conterrà l'indirizzo del primo elemento del nostro vettore, e possiamo leggere gli elementi successivi semplicemente incrementando il suo valore. Se infatti ora andiamo a leggere 5 int a partire da v usando un debugger otterremo proprio

(gdb) x/5x v
0xbf92a378:     0x00000000      0x00000001      0x00000002      0x00000003
0xbf92a388:     0x00000004

[modifica] Istruzione call: Chiamate a funzioni in Assembly

La call è l'istruzione a basso livello usata per richiamare una qualsiasi funzione. Una funzione, a basso livello, viene trattata come una semplice etichetta, ad esempio una printf sarà qualcosa del tipo

printf:
   istruzioni
   .......

e una call è molto simile concettualmente ad una semplice jmp. La differenza è che la call prima di saltare all'etichetta indicata salva sullo stack l'indirizzo dell'istruzione successiva da eseguire, contenuto nel registro EIP, in modo da sapere da dove riprendere l'esecuzione del codice quando la funzione richiamata ritorna, quindi effettua il salto vero e proprio. A livello concettuale, un

call   func

è equivalente a un

push   %eip   ; Salvo l'indirizzo da cui ripartire dopo la chiamata della funzione
jmp    func   ; Salto all'etichetta contenente il codice della funzione

Ovviamente questo codice è valido solo a livello concettuale...l'assemblatore non lo accetterà mai in quanto il registro EIP non è direttamente modificabile dal programmatore, anzi non è nemmeno visibile dal codice, ma è un pezzo di codice che serve per capire cosa succede a basso livello quando nel codice viene incontrata una call. Allo stesso modo, la funzione sarà strutturata nel seguente modo:

func:
   .......
   .......
   ret

Il ret finale dice di ritornare al chiamante. Semplicemente, riprende dallo stack l'indirizzo salvato in precedenza dal chiamante e salta lì.

[modifica] Passaggio di parametri a funzioni

Ora è anche comprensibile come funziona a basso livello il passaggio di parametri a funzioni. Un parametro è semplicemente un valore che viene salvato sullo stack prima della chiamata della funzione, e può essere poi prelevato direttamente dallo stack all'interno del codice stesso della funzione. Esempio, se ad una mia funzione voglio passare il valore 1:

pushl   $1
call    func
 
.......
 
func:
movl    4(%esp),%eax

Semplicemente, salvo sullo stack il valore che voglio passare e richiamo la funzione. A questo punto prendo il valore salvato all'indirizzo [ESP+4] e lo copio in EAX: vedremo che in EAX sarà presente proprio il valore 1 che il chiamante ha passato alla funzione. Dovrebbe anche essere chiaro perché per prelevare il primo parametro passato alla funzione vado a leggere all'indirizzo [ESP+4]...il chiamante effettua una push del parametro da passare, ma subito dopo c'è una call, che a sua volta effettua un'altra push, salvando sullo stack il valore di EIP (indirizzo a cui riportare l'esecuzione del programma una volta terminata la funzione). Quando entro nel codice di func la situazione dello stack sarà quindi qualcosa del tipo

+-------------------------------+
| Indirizzo di ritorno (4 byte) |  <--- ESP
+-------------------------------+
|       Parametro passato       |  <--- ESP+4
+-------------------------------+

Poiché ESP punta alla cima dello stack, punterà all'indirizzo in cui è salvato l'indirizzo di ritorno. Se invece voglio leggere il parametro passato, devo andare a leggere il valore presente a ESP+4. Se alla funzione volessi passare invece di uno, due parametri interi (quindi a 4 byte), il secondo sarebbe situato a [ESP+4], e il primo a [ESP+8] (dato che vengono salvati in ordine inverso in virtù della caratteristica LIFO dello stack, quindi prima il secondo e poi il primo).

È proprio in questo modo che vengono passati i parametri alle funzioni che richiamiamo quotidianamente dai nostri codici scritti in linguaggio ad alto livello. Ad esempio, una

printf ("%d\n",n);

in Assembly si traduce come una

format:   .string   "%d\n"
n:        .long   (valore)
 
......
 
pushl   n
pushl   $format
call    printf
addl    $8,%esp

I parametri, come al solito, vengono salvati in ordine inverso. Si noti la buona norma di sommare alla fine, quando i dati salvati sullo stack non servono più, al registro ESP tante unità quanti sono i byte scritti in precedenza, per dire alla macchina che quella zona di memoria è ora libera.

Potete testare, volendo, il codice riportato sopra di persona, includendo in testa al sorgente stdio.h, come si farebbe con un normale codice C, e compilandolo normalmente con gcc. A sorpresa, avrete richiamato una printf in Assembly.

#include <stdio.h>
 
.text
format:   .string  "La variabile n=%d e' all'indirizzo 0x%x\n"
n:        .long    3
 
.global main
main:
        push    $n
        push    n         ; Si noti la differenza. Con n salvo il valore di n, con $n il suo indirizzo
        push    $format
        call    printf
        add     $12,%esp  ; Sommo a ESP 4*3=12 byte
 
        mov     $1,%eax
        mov     $0,%ebx
        int     $0x80
 
        leave
        ret

[modifica] Valori di ritorno

Possiamo già intuire come funzioni a basso livello il ritorno di valori di una funzione. Per convenzione, il valore di ritorno viene scritto dalla funzione in EAX. Il codice della funzione che abbiamo visto prima quindi

foo:
        mov    4(%esp),%eax
        ret

non fa altro che prendere il parametro passato alla funzione, salvarlo in EAX e ritornare. Quindi, ad alto livello potrebbe corrispondere al codice di una funzione del tipo

int foo (int n)  {
  return n;
}