Call stack: differenze tra le versioni

Versione delle 06:29, 10 lug 2008

Versione attuale delle 21:52, 25 set 2024

(44 versioni intermedie di 33 utenti non mostrate)

Riga 1:

{{F|programmazione|febbraio 2013}}

{{T|lingua=inglese|argomento=informatica|data=marzo 2007}}

[[ImmagineFile:Call stack layout.svg|centerthumb|Esempio]]

In [[informatica]], un '''call stack''' (dall'inglese ''pila di chiamate'') è uno [[stack]] (ovvero una specie di pila) che immagazzina informazioni sulle [[subroutine]] attive del [[computer]] (le subroutine attive sono quelle che sono state chiamate ma la cui esecuzione non è terminata). Questo tipo di pila è spesso chiamato anche execution stack, control stack, function stack, o run-time stack e spesso semplicemente "stack".

In [[informatica]], un '''''call stack''''' (traducibile letteralmente dall'[[Lingua inglese|inglese]] come "pila delle chiamate") è una zona di memoria di un programma, organizzata in forma di [[Pila (informatica)|stack]], nella quale sono immagazzinate le informazioni sulle ''[[subroutine]]'' attive in un dato momento (le ''subroutine'' attive sono quelle che sono state invocate ma la cui esecuzione non è terminata). Può essere tradotto come stack delle invocazioni a funzione (o chiamate a funzione) o stack delle invocazioni a metodo (o chiamate a metodo) a seconda del tipo di ''subroutine'' coinvolto.

Questo tipo di pila è spesso chiamato anche '''execution stack''', '''control stack''', '''function stack''', o '''run-time stack''', oppure, quando non vi è possibilità di confusione, semplicemente '''stack'''.

Una call stack può essere usata per molti scopi, ma la ragione principale per usarla è tenere traccia dei punti in cui ogni subroutine attiva dovrebbe restituire il controllo quando termina l'esecuzione. Se, per esempio, una subroutine DrawSquare (disegna un quadrato) chiama la subroutine DrawLine (disegna una linea) da quattro diversi punti, il codice di DrawLine deve poter conoscere a quale punto tornare terminata l'esecuzione. Questo compito è svolto tipicamente dal codice per ogni chiamata all'interno di DrawSquare inserendo l'indirizzo dell'[[istruzione]] dopo una particolare dichiarazione di chiamata ("return address" o indirizzo di ritorno) all'interno del call stack.

L'insieme delle informazioni specifiche di una ''subroutine'' all'interno di un ''call stack'' è detto ''frame''.

Poiché il call stack è organizzato come una pila, la [[Funzione (informatica)|funzione]] chiamante mette l'indirizzo di ritorno sopra la pila e la subroutine chiamata, quando termina, toglie l'indirizzo di ritorno dalla pila e trasferisce il controllo a quell'indirizzo. Se una subroutine chiamata chiama un'altra subroutine, essa metterà l'indirizzo di ritorno sopra la call stack e così via le informazioni vengono accatastate e rimosse come previsto dal [[programma (informatica)|programma]]. Se viene usato tutto lo spazio a disposizione del call stack, si verifica un errore chiamato [[stack overflow]]. Aggiungere una subroutine nel call stack è definito [[winding]]; toglierla è definito unwinding.

== Funzionamento ==

C'è solitamente solo un call stack associato con un [[programma (informatica)|programma]] in esecuzione (o più precisamente con ogni [[task]] o [[thread]] di un processo), tuttavia stack aggiuntivi possono essere creati per gestire [[segnale|segnali]] o per il [[multitasking]] cooperativo. Poiché ne esiste uno solo in questo importante contesto, ci si riferisce semplicemente allo stack (implicitamente "del task").

UnaIl call stack può essere usatamotivo per molticui scopi,è manecessario laadottare ragioneun principale''call per usarlastack'' è tenere traccia dei punti in cui ogni ''subroutine'' attiva dovrebbe restituire il controllo quando termina l'esecuzione. Se, per esempio, una ''subroutine'' <code>DrawSquare</code> (disegna un quadrato) chiama la ''subroutine'' <code>DrawLine</code> (disegna una linea) da quattro diversi punti, il codice di <code>DrawLine</code> deve poter conoscere a quale punto tornare terminata l'esecuzione. Questo compito è svolto tipicamente dal codice per ogni chiamata all'interno di <code>DrawSquare</code> inserendo l'indirizzo dell'[[istruzione]] dopo una particolare dichiarazione di chiamata ("''return address"'' o indirizzo di ritorno) all'interno del ''call stack''.

Poiché il ''call stack'' è organizzato come una pila, la [[Funzione (informatica)|funzione]] chiamante mette l'indirizzo di ritorno sopra la pila e la ''subroutine'' chiamata, quando termina, toglie l'indirizzo di ritorno dalla pila e trasferisce il controllo a quell'indirizzo. Se una ''subroutine'' chiamata chiama un'altra ''subroutine'', essa metterà l'indirizzo di ritorno sopra la ''call stack'' e così via le informazioni vengono accatastate e rimosse come previsto dal [[programma (informatica)|programma]]. Se viene usato tutto lo spazio a disposizione del ''call stack'', si verifica un errore chiamato [[stack overflow]]. Aggiungere una ''subroutine'' nel ''call stack'' è definito [[''winding]]''; toglierla è definito ''unwinding''.

Nei [[linguaggio di programmazione|linguaggi di programmazione]] di alto livello, le specifiche del call stack sono nascoste solitamente dal [[programmatore]]. Egli fornisce accesso solo alla lista delle funzioni e non alla memoria dello stack stesso. Molti linguaggi [[Assembly]] d'altra parte, richiedono ai programmatori di essere coinvolti nella gestione dello stack. I dettagli dello stack in un linguaggio di programmazione dipendono anche dal compilatore, dal sistema operativo e dalle istruzioni disponibili.

C'è solitamente solo un ''call stack'' associato con un [[programma (informatica)|programma]] in esecuzione (o più precisamente con ogni [[task]] o [[thread (informatica)|thread]] di un processo), tuttavia stack aggiuntivi possono essere creati per gestire [[segnale (informatica)|segnali]] o per il [[multitasking]] cooperativo. Poiché ne esiste uno solo in questo importante contesto, ci si riferisce semplicemente allo stack (implicitamente "del task").

== Scopi del call stack ==

Nei [[linguaggio di programmazione|linguaggi di programmazione]] di alto livello, le specifiche del ''call stack'' sono nascoste solitamente dalal [[programmatore]]. EgliQuest'ultimo fornisceha accesso solo alla lista delle funzioni e non alla memoria dellooccupata dallo stack, né alla struttura interna stessoadottata. Molti linguaggi [[Assemblyassembly]] d'altra parte, richiedono ai programmatori di essere coinvolti nella gestione dello stack. I dettagli dello stack in un linguaggio di programmazione dipendono anche dal [[compilatore]], dal sistema operativo e dalle istruzioni disponibili.

Come descritto sopra, lo scopo primario del call stack è:

== Scopi del call stack ==

* '''immagazzinare gli indirizzi di ritorno''' - Quando una subroutine viene chiamata, l'indirizzo dell'istruzione di ritorno deve essere salvato da qualche parte. Utilizzando una pila per salvare gli indirizzi di ritorno si hanno importanti vantaggi rispetto alle alternative. Uno di questi è che ogni task ha il proprio stack e pertanto le subroutine possono essere "rientranti" e quindi possono essere attive simultaneamente per task diversi che fanno cose diverse. Un altro vantaggio è che la [[ricorsione]] è automaticamente supportata. Quando una funzione chiama sé stessa ricorsivamente, un indirizzo di ritorno necessita di essere registrato per ogni attivazione della funzione così da poter essere usato per il ritorno da ogni attivazione della funzione. Questa capacità è automatica con un stack.

Come descritto sopra, loLo scopo primario del ''call stack'' è:

* '''immagazzinare gli indirizzi di ritorno''' - Quando una ''subroutine'' viene chiamata, l'indirizzo dell'istruzione di ritorno deve essere salvato da qualche parte. Utilizzando una pila per salvare gli indirizzi di ritorno si hanno importanti vantaggi rispetto alle alternative. Uno di questi è che ogni task ha il proprio stack e pertanto le ''subroutine'' possono essere "rientranti" e quindi possono essere attive simultaneamente per task diversi che fanno cose diverse. Un altro vantaggio è che la [[ricorsione]] è automaticamente supportata. Quando una funzione chiama sé stessa ricorsivamente, un indirizzo di ritorno necessita di essere registrato per ogni attivazione della funzione così da poter essere usato per il ritorno da ogni attivazione della funzione. Questa capacità è automatica con un stack.

Un call stack può avere scopi aggiuntivi, dipendenti dal linguaggio, dal sistema operativo e dall'ambiente della macchina. Tra questi:

* '''immagazzinare dati locali''' - Una subroutine frequentemente necessita di spazio di memoria per registrare i valori delle variabili locali, le variabili usate solo nella subroutine attiva e che non devono trattenere valori dopo il ritorno (alla funzione chiamante). È spesso conveniente per allocare spazio per questo uso spostarsi semplicemente in cima allo stack in modo sufficiente ad avere lo spazio. È molto veloce paragonato, ad esempio, con l'allocazione di tipo [[Allocazione_dinamica_della_memoria|heap]]. Ogni diversa attivazione di una subroutine ha il proprio spazio separato nello stack per i dati locali.

* '''passaggio di parametri''' - Le subroutine spesso richiedono che i valori dei parametri siano forniti dal codice che le chiama e non è raro che lo spazio per questi parametri possa essere nel call stack. Generalmente se ci sono solo pochi piccoli parametri, i registri del [[processore]], possono essere usati per il passaggio dei valori, ma se ci sono più parametri da gestire in questo modo, è necessario spazio in memoria. Il call stack lavora meglio come posto per questi parametri, specialmente poiché ogni chiamata della subroutine, che avrà diversi valori dei parametri, avrà uno spazio separato nel call stack per questi valori.

* '''stack di valutazione''' - Gli [[operandi]] per operazioni aritmetiche e logiche sono spesso inseriti nel [[registro]] e utilizzati là. Comunque, in alcune situazioni gli operandi possono essere accatastati ad una profondità arbitraria, il che significa che deve essere usato qualcosa di più del registro. Lo stack di questi operandi, similmente ai calcolatori di tipo RPN, è chiamato stack di valutazione (evaluation stack) e può occupare spazio nel call stack.

* '''puntatore dell'istanza corrente''' - Alcuni linguaggi orientati agli oggetti (come [[C++]]), immagazzinano questo puntatore come argomento delle funzioni nel call stack quando invocano un metodo. Questo puntatore punta all'istanza dell'oggetto a cui è associato il metodo invocato. È una parte essenziale del contesto di esecuzione di linguaggi orientati agli oggeti, poiché fornisce accesso ai dati posseduti dall'oggetto corrente. Questo puntatore è collegato a livelli utilizzati nella programmazione orientata agli oggetti con livelli (tipi di strutture stack) della run-time call stack.

* '''Ambiente dei contenitori di subroutines''' - Alcuni linguaggi di programmazione (come [[Pascal (programmazione)|Pascal]] e [[Ada (programmazione)|Ada]]) supportano [[Funzioni annidate|subroutines annidate]], permettendo ad una routine interna di accedere al contesto della sua routine contenitore, cioè' ai parametri e alle variabili locali nell'ambiente della routine esterna. Tali lingue generalmente permettono alle routines di effettuare chiamate ricorsive (la funzione richiama se stessa), ottenendo multiple call stacks per le chiamate di routines delle routines interne, ciascuna delle quali punta sullo stesso ambiente della routine esterna. Questo tipo di call frame è anche conosciuto come ''display''.

<!--DA TRADURRE

* '''Altro return state''' – Besides the return address, in some environments there may be other machine or software states that need to be restored when a subroutine returns. This might include things like privilege level, exception handling information, arithmetic modes, and so on. If needed, this may be stored in the call stack just as the return address is.

The typical call stack is used for the return address, locals, and parameters (known as a ''call frame''). In some environments there may be more or fewer functions assigned to the call stack. In the [[Forth (programming language)|Forth programming language]], for example, only the return address and local variables are stored on the call stack (which in that environment is named the ''return stack''); parameters are stored on a separate ''data stack''. Most Forths also have a third stack for [[floating point]] parameters.

==Structure==

A call stack is composed of '''stack frames''' (sometimes called '''activation records'''). Each stack frame corresponds to a call to a subroutine which has not yet terminated with a return. For example, if a subroutine named <code>DrawLine</code> is currently running, having just been called by a subroutine <code>DrawSquare</code>, the top part of the call stack might be laid out like this (where the stack is growing towards the top):

[[Immagine:Call stack layout.svg|center]]

The stack frame at the top of the stack is for the currently executing routine. In the most common approach the stack frame includes space for the local variables of the routine, the return address back to the routine's caller, and the parameter values passed into the routine. The memory locations within a frame are often accessed via a register called the '''stack pointer''', which also serves to indicate the current top of the stack. Alternatively, memory within the frame may be accessed via a separate register, often termed the '''frame pointer''', which typically points to some fixed point in the frame structure, such as the ___location for the return address.

Stack frames are not all the same size. Different subroutines have differing numbers of parameters, so that part of the stack frame will be different for different subroutines, although usually fixed across all activations of a particular subroutine. Similarly, the amount of space needed for local variables will be different for different subroutines. In fact, some languages support dynamic allocations of memory for local variables on the stack, in which case the size of the locals area will vary from activation to activation of a subroutine, and is not known when the subroutine is [[compiler|compiled]]. In the latter case, access via a frame pointer, rather than via the stack pointer, is usually necessary since the offsets from the stack top to values such as the return address would not be known at compile time.

In many systems a stack frame has a field to contain the previous value of the frame pointer register, the value it had while the caller was executing. For example, in the diagram above, the stack frame of <code>DrawLine</code> would have a memory ___location holding the frame pointer value that <code>DrawSquare</code> uses. The value is saved upon entry to the subroutine and restored for the return. Having such a field in a known ___location in the stack frame allows code to access each frame successively underneath the currently executing routine's frame.

Programming languages that support [[nested function|nested subroutines]] have a field in the call frame that points to the call frame of the outer routine that invoked the inner (nested) routine. This is also called a '''display'''. This pointer provides the inner routine (as well as any other inner routines it may invoke) access to the parameters and local variables of the outer invoking routine.

For some purposes, the stack frame of a subroutine and that of its caller can be considered to overlap, the overlap consisting of the area where the parameters are passed from the caller to the callee. In some environments, the caller pushes each argument onto the stack, thus extending its stack frame, then invokes the callee. In other environments, the caller has a preallocated area at the top of its stack frame to hold the arguments it supplies to other subroutines it calls. This area is sometimes termed the '''outgoing arguments area''' or '''callout area'''. Under this approach, the size of the area is calculated by the compiler to be the largest needed by any called subroutine.

==Use==

===Call site processing===

Usually the call stack manipulation needed at the site of a call to a subroutine is minimal (which is good since there can be many call sites for each subroutine to be called). The values for the actual arguments are evaluated at the call site, since they are specific to the particular call, and either pushed onto the stack or placed into registers, as determined by the [[calling convention]] being used. The actual call instruction, such as "Branch and Link," is then typically executed to transfer control to the code of the target subroutine.

===Callee processing===

In the called subroutine, the first code executed is usually termed the [[function prologue|subroutine prologue]], since it does the necessary housekeeping before the code for the statements of the routine is begun.

The prologue will commonly save the return address left in a register by the call instruction by pushing the value onto the call stack. Similarly, the current stack pointer and/or frame pointer values may be pushed. Alternatively, some instruction set architectures automatically provide comparable functionality as part of the action of the call instruction itself, and in such an environment the prologue need not do this.

If frame pointers are being used, the prologue will typically set the new value of the frame pointer register from the stack pointer. Space on the stack for local variables can then be allocated by incrementally changing the stack pointer.

The [[Forth (programming language)|Forth programming language]] allows explicit winding of the call stack (called there the "return stack"). The [[Scheme (programming language)|Scheme programming language]] allows the winding of special frames on the stack through a "[[dynamic wind]]".

===Return processing===

When a subroutine is ready to return, it executes an epilogue that undoes the steps of the prologue. This will typically restore saved register values (such as the frame pointer value) from the stack frame, pop the entire stack frame off the stack by changing the stack pointer value, and finally branch to the instruction at the return address. Under many calling conventions the items popped off the stack by the epilogue include the original argument values, in which case there usually are no further stack manipulations that need to be done by the caller. With some calling conventions, however, it is the caller's responsibility to remove the arguments from the stack after the return.

===Unwinding===

Returning from the called function will pop the top frame off of the stack, perhaps leaving a return value.

Some languages (such as Pascal) allow a global [[GOTO|goto]] statement to transfer control out of a nested function and into a previously invoked outer function. This operation requires the stack to be unwound, removing as many stack frames as necessary to restore the proper context to transfer control to the target statement within the enclosing outer function. Such transfers of control are generally used only for error handling.

Other languages provide [[exception handling]], which also requires unwinding of the stack. The stack frame of a function contains one or more entries specifying exception handlers. When an exception is thrown, the stack is unwound until an exception handler is found that is prepared to handle (catch) the exception. [[Common Lisp]] allows control of what happens when the stack is unwound by using the <code>unwind-protect</code> special operator.

When applying a [[continuation]], the stack is unwound and then rewound with the stack of the continuation. This is not the only way to implement continuations; for example, using multiple, explicit stacks, application of a continuation can simply activate its stack and wind a value to be passed.

Un ''call stack'' può avere scopi aggiuntivi, dipendenti dal linguaggio, dal sistema operativo e dall'ambiente della macchina. Tra questi:

==Security==

* '''immagazzinare dati locali''' - Una ''subroutine'' frequentemente necessita di spazio di memoria per registrare i valori delle variabili locali, le variabili usate solo nella ''subroutine'' attiva e che non devono trattenere valori dopo il ritorno (alla funzione chiamante). È spesso conveniente per allocare spazio per questo uso spostarsi semplicemente in cima allo stack in modo sufficiente ad avere lo spazio. È molto veloce paragonato, ad esempio, con l'allocazione di tipo [[Allocazione_dinamica_della_memoriaAllocazione dinamica della memoria|heap]]. Ogni diversa attivazione di una ''subroutine'' ha il proprio spazio separato nello stack per i dati locali.

The mixing of control flow data affecting the execution of code (return addresses, saved frame pointers) and simple program data (parameters, return values) in a call stack is a security risk, possibly [[exploit (computer security)|exploit]]able through [[buffer overflow]]s (in which article the risk and exploitation are explained).

* '''passaggio di parametri''' - Le ''subroutine'' spesso richiedono che i valori dei parametri siano forniti dal codice che le chiama e non è raro che lo spazio per questi parametri possa essere nel ''call stack''. Generalmente se ci sono solo pochi piccoli parametri, i registri del [[processore]], possono essere usati per il passaggio dei valori, ma se ci sono più parametri da gestire in questo modo, è necessario spazio in memoria. Il ''call stack'' lavora meglio come posto per questi parametri, specialmente poiché ogni chiamata della ''subroutine'', che avrà diversi valori dei parametri, avrà uno spazio separato nel ''call stack'' per questi valori.

-->

* '''stack di valutazione''' - Gli [[operandi]] per operazioni aritmetiche e logiche sono spesso inseriti nel [[registro (informatica)|registro]] e utilizzati là. Comunque, in alcune situazioni gli operandi possono essere accatastati ada una profondità arbitraria, il che significa che deve essere usato qualcosa di più del registro. Lo stack di questi operandi, similmente ai calcolatori di tipo [[Notazione polacca inversa|RPN]], è chiamato stack di valutazione (''evaluation stack'') e può occupare spazio nel ''call stack''.

* '''puntatore dell'istanza corrente''' - Alcuni linguaggi orientati agli oggetti (come [[C++]]), immagazzinano questo puntatore come argomento delle funzioni nel ''call stack'' quando invocano un metodo. Questo puntatore punta all'istanza dell'oggetto a cui è associato il metodo invocato. È una parte essenziale del contesto di esecuzione di linguaggi orientati agli oggetioggetti, poiché fornisce accesso ai dati posseduti dall'oggetto corrente. Questo puntatore è collegato a livelli utilizzati nella [[programmazione orientata agli oggetti]] con livelli (tipi di strutture stack) della [[run-time]] ''call stack''.

* '''Ambiente dei contenitori di subroutines''subroutine'' - Alcuni linguaggi di programmazione (come [[Pascal (programmazione)|Pascal]] e [[Ada (linguaggio di programmazione)|Ada]]) supportano [[FunzioniAnnidamento annidate(informatica)|subroutines''subroutine'' annidate]], permettendo ada una ''routine'' interna di accedere al contesto della sua routine contenitore, cioè' ai parametri e alle variabili locali nell'ambiente della ''routine'' esterna. Tali lingue generalmente permettono alle routines''routine'' di effettuare chiamate ricorsive (la funzione richiama se stessa), ottenendo multiple ''call stacksstack'' per le chiamate di routines''routine'' delle routines''routine'' interne, ciascuna delle quali punta sullo stesso ambiente della ''routine'' esterna. Questo tipo di ''call frame'' è anche conosciuto come ''display'''''.'''

== Voci correlate ==

* [[StackPila (informatica)]]

* [[Subroutine]]

* [[Allocazione dinamica della memoria]]

* [[Memoria allocata dinamicamente]]

* [[Stack trace]]

{{Portale|Informaticainformatica}}

[[Categoria:Gestione della memoria]]

[[en:Call stack]]

[[es:Pila (estructura de datos)#Pila de llamadas]]

[[fr:Pile (informatique)#Pile d'appel]]

[[is:Kallhlaði]]

[[ja:コールスタック]]

[[pt:Pilha de chamada]]

[[ru:Стек вызовов]]

[[sv:Stackpekare]]