Casa > Esposizione > Contenuto
Categorie di prodotti

Contattaci

Aggiungi: Block 5, Fuqiang Technology Park, Zhugushi Road, Wulian, Longgang 518116

Mob: + 86-13510459036

E-mail: info@panadisplay.com

Registro di visualizzazione o struttura dati, per individuare le strutture di stack di funzioni annidate nella programmazione del computer
Apr 22, 2017

Stack di chiamata

Nella scienza dell'informatica , una stack di chiamate è una struttura di dati di stack che memorizza le informazioni sulle sottoprogrammi attivi di un programma di computer . Questo tipo di stack è anche conosciuto come stack di esecuzione , stack di programmi , stack di controllo , stack di run-time o stack della macchina e spesso viene abbreviato solo "lo stack". Anche se la manutenzione dello stack di chiamate è importante per il corretto funzionamento del software , i dettagli sono normalmente nascosti e automatici nei linguaggi di programmazione ad alto livello . Molti set di istruzioni informatici forniscono istruzioni speciali per la manipolazione delle pile.

Una stack di chiamata viene utilizzata per diversi scopi correlati, ma la ragione principale per averne è quella di tenere traccia del punto in cui ogni sottoprogramma attivo dovrebbe restituire il controllo quando termina l'esecuzione. Una subroutine attiva è quella che è stata chiamata, ma deve ancora completare l'esecuzione, dopo di che il controllo deve essere restituito al punto di chiamata. Tali attivazioni di subroutine possono essere nidificate a qualsiasi livello (ricorsivo come caso speciale), quindi la struttura delle stack. Se ad esempio una subroutine DrawSquare chiama una sottoprogetto DrawLine da quattro diversi luoghi, DrawLine deve sapere dove tornare quando la sua esecuzione viene completata. Per eseguire questo, l' indirizzo che segue l' istruzione di chiamata, l' indirizzo di ritorno , viene premuto sulla stack di chiamata con ciascuna chiamata.


Contenuto

[ Nascondi ]


Descrizione [ modifica ]

Poiché lo stack di chiamata è organizzato come una pila , il chiamante sposta l'indirizzo di ritorno sulla pila e la sottoprogramma chiamata, quando finisce, tira o pone l'indirizzo di ritorno fuori dalla pila di chiamate e trasferisce il controllo a tale indirizzo. Se una subroutine chiamata richiama ancora un'altra sottoprogramma, spingerà un altro indirizzo di ritorno sullo stack di chiamata e così via, con le informazioni che si impilano e si disattivano come il programma prescrive. Se la spinta consuma tutto lo spazio assegnato per lo stack di chiamata, si verifica un errore chiamato overflow dello stack , in genere causando il crash del programma. L'aggiunta di una voce del sottoprogramma alla stack di chiamata viene chiamata "avvolgimento"; Al contrario, la rimozione delle voci è "unwinding".

Di solito è esattamente uno stack di chiamata associato a un programma in esecuzione (o più accuratamente, con ogni attività o thread di un processo ), anche se possono essere creati ulteriori stack per la gestione del segnale o il multitasking cooperativo (come con setcontext ). Dal momento che esiste solo uno in questo contesto importante, può essere indicato come lo stack (implicitamente, "del compito"); Tuttavia, nel linguaggio di programmazione Forth è possibile accedere più a livello dello stack di dati o dello stack di parametri rispetto allo stack di chiamate e viene comunemente indicato come stack (vedi sotto).

Nei linguaggi di programmazione ad alto livello , le specifiche dello stack di chiamata sono di solito nascoste dal programmatore. Essi hanno accesso solo a una serie di funzioni e non alla memoria dello stack stesso. Questo è un esempio di astrazione . La maggior parte delle lingue di montaggio , d'altra parte, richiede che i programmatori siano coinvolti nella manipolazione della pila. I dettagli effettivi dello stack in un linguaggio di programmazione dipendono dal compilatore , dal sistema operativo e dal set di istruzioni disponibili.

Funzioni dello stack di chiamata [ modifica ]

Come indicato in precedenza, lo scopo principale di una stack di chiamata è quello di memorizzare gli indirizzi di ritorno . Quando viene chiamata una subroutine, è necessario salvare da qualche parte la posizione (indirizzo) dell'istruzione in cui può essere ripresa in seguito. L'utilizzo di una pila per salvare l'indirizzo di ritorno ha importanti vantaggi rispetto alle convenzioni di chiamata alternative. Uno è che ogni attività può avere una propria pila, e quindi la subroutine può essere reentrante , cioè può essere attiva contemporaneamente per vari compiti che svolgono cose diverse. Un altro vantaggio è che la ricorsione viene supportata automaticamente. Quando una funzione si chiama in modo ricorsivo, occorre memorizzare un indirizzo di ritorno per ogni attivazione della funzione in modo da poter essere utilizzata in seguito per tornare dall'attivazione della funzione. Le strutture dello stack forniscono questa funzionalità automaticamente.

A seconda della lingua, del sistema operativo e dell'ambiente macchina, uno stack di chiamata può servire a scopi aggiuntivi, tra cui ad esempio:

Memorizzazione dati locale


Una subroutine ha spesso bisogno di spazio di memoria per memorizzare i valori delle variabili locali , le variabili note solo nell'ambito della subroutine attiva e non mantenere i valori dopo la restituzione. È spesso conveniente allocare spazio per questo utilizzo semplicemente spostando la parte superiore dello stack sufficiente per fornire lo spazio. Questo è molto veloce se confrontato con l'allocazione della memoria dinamica , che utilizza lo spazio heap . Si noti che ogni attivazione separata di una subroutine ha il proprio spazio separato nella pila per i locals.


Passaggio dei parametri


Le subroutine richiedono spesso che i valori dei parametri siano forniti dal codice che li chiama e non è raro che lo spazio per questi parametri possa essere definito nello stack di chiamate. Generalmente, se ci sono solo pochi parametri, verranno utilizzati i registri del processore per passare i valori, ma se ci sono più parametri che possono essere gestiti in questo modo, sarà necessario lo spazio di memoria. Lo stack di chiamata funziona bene come un luogo per questi parametri, specialmente perché ogni chiamata a una subroutine, che avrà valori diversi per i parametri, sarà dato spazio separato nello stack di chiamata per questi valori.


Stack di valutazione


Gli operandi per le operazioni aritmetiche o logiche vengono spesso collocate in registri e operano lì. Tuttavia, in alcune situazioni gli operandi possono essere impilati fino ad una profondità arbitraria, il che significa qualcosa di più che i registri devono essere utilizzati (questo è il caso della rottura del registro ). La pila di tali operandi, piuttosto come quella in una calcolatrice RPN , viene chiamata pila di valutazione e può occupare spazio nello stack di chiamate.


Puntatore all'istanza corrente


Alcuni linguaggi orientati agli oggetti (ad es. C + + ) memorizzano questo puntatore con argomenti di funzione nello stack di chiamata quando invocano i metodi. Questo puntatore indica l' istanza di oggetto associata al metodo da invocare.


Contenitore di contesto subroutine


Alcuni linguaggi di programmazione (ad esempio, Pascal e Ada ) supportano la dichiarazione di sottoprogrammi nidificati , i quali sono autorizzati ad accedere al contesto delle loro routine di chiusura, vale a dire i parametri e le variabili locali nell'ambito delle routine esterne. Tale annidamento statico può ripetere - una funzione dichiarata all'interno di una funzione dichiarata all'interno di una funzione ... L'implementazione deve fornire un mezzo attraverso il quale una funzione chiamata a un determinato livello di nidificazione statica può riferirsi alla cornice racchiusa ad ogni livello di nidificazione che racchiude. Normalmente questo riferimento viene implementato da un puntatore nella cornice dell'ultima istanza attivata della funzione di chiusura, chiamata "link downstack" o "collegamento statico", per distinguerlo dal "collegamento dinamico" che si riferisce al chiamante immediato ( Che non devono essere la funzione statica statale).


Invece di un collegamento statico, i riferimenti ai frame statici inclusi possono essere raccolti in una matrice di puntatori conosciuti come un display indicizzato per individuare un frame desiderato. La profondità del nesting lessicale di una routine è una costante nota, quindi la dimensione di un display di routine è fisso. Inoltre, è noto il numero di ambiti contenenti traverse, anche l'indice sul display è fisso. Di solito un display di routine si trova nella propria cornice di pile, ma il Burroughs B6500 ha implementato un tale display in hardware che ha supportato fino a 32 livelli di nesting statico.


Le voci di visualizzazione che indicano gli ambiti contenenti si ottengono dal prefisso appropriato del display del chiamante. Una routine interna che ricorre crea frame separati di chiamata per ogni invocazione. In questo caso, tutti i collegamenti statici della routine interna indicano lo stesso contesto di routine esterno.


Altri stati di ritorno


Oltre all'indirizzo di ritorno, in alcuni ambienti possono essere altri stati di macchina o software che devono essere ripristinati quando viene restituito un subroutine. Ciò potrebbe includere cose come il livello di privilegio, le informazioni relative alla gestione delle eccezioni, le modalità aritmetiche e così via. Se necessario, questo può essere memorizzato nello stack di chiamata proprio come l'indirizzo di ritorno.


Lo stack chiamante tipico viene utilizzato per l'indirizzo di ritorno, i locals e i parametri (noto come un frame di chiamata ). In alcuni ambienti potrebbe essere assegnato più o meno funzioni allo stack di chiamate. Nel linguaggio di programmazione Forth , ad esempio, normalmente solo gli indirizzi di ritorno, i parametri e gli indici contati e eventualmente le variabili locali vengono memorizzati nello stack di chiamata (che in quell'ambiente viene chiamato lo stack di ritorno ), anche se i dati possono essere temporaneamente posizionati Usando un codice speciale di gestione delle stack di ritorno finché le esigenze delle chiamate e dei ritorni sono rispettati; I parametri vengono normalmente memorizzati su uno stack di dati o stack di parametri separati, tipicamente chiamati stack nella terminologia Forth anche se c'è una stack di chiamata poiché è di solito accessibile in modo più esplicito. Alcuni Forth hanno anche una terza stack per i parametri a virgola mobile .

Struttura [ modifica ]

Layout delle stazioni di chiamata

Una stack di chiamate è composta da fotogrammi di stack (chiamati anche record di attivazione o frame di attivazione ). Questi sono strutture di dati dipendenti dalla macchina e ABI- dipendenti che contengono informazioni di stato subroutine. Questi dati sono a volte denominati CFI (Call Frame Information). [1] Ogni frame dello stack corrisponde a una chiamata a una sottoprogramma che non è ancora terminata con un ritorno. Ad esempio, se una sottoprogramma denominata DrawLine è attualmente in esecuzione, essendo stata chiamata da una subroutine DrawSquare , la parte superiore dello stack di chiamata potrebbe essere disegnata come nell'immagine a destra.

Un diagramma simile può essere disegnato in entrambe le direzioni fino a quando si intende il posizionamento della parte superiore, e quindi la direzione della crescita dello stack. Inoltre, a prescindere da ciò, le architetture differiscono per quanto riguarda la crescita delle stazioni di chiamata verso indirizzi più alti o verso indirizzi inferiori. La logica del diagramma è indipendente dalla scelta di indirizzamento.

Il frame dello stack nella parte superiore dello stack è per la routine attualmente eseguita. Il frame della pila comprende solitamente almeno i seguenti elementi (in ordine di spostamento):

  • Gli argomenti (valori dei parametri) passati alla routine (se esistono);

  • L'indirizzo di ritorno indietro al chiamante della routine (ad esempio nel frame Stack di DrawLine , un indirizzo nel codice di DrawSquare ); e

  • Spazio per le variabili locali della routine (se presente).

Puntatori di pila e cornice [ modifica ]

Quando le dimensioni dei frame dello stack possono differire, come tra le diverse funzioni o tra le invocazioni di una determinata funzione, sbloccare un fotogramma dalla stack non costituisce un decremento fisso del puntatore di stack . Al ritorno della funzione, invece, il puntatore della pila viene ripristinato al puntatore del frame , il valore del puntatore dello stack appena prima della chiamata della funzione. Ogni frame della pila contiene un puntatore di pila alla parte superiore del fotogramma immediatamente sottostante. Il puntatore dello stack è un registro mutevole condiviso tra tutte le invocazioni. Un puntatore del frame di una data invocazione di una funzione è una copia del puntatore dello stack come era prima che la funzione venisse invocata. [2]

Le posizioni di tutti gli altri campi del fotogramma possono essere definite relative alla parte superiore del fotogramma, come offset negative del puntatore dello stack o relative alla parte superiore del fotogramma sottostante, come offset positivi del puntatore del fotogramma. La posizione del puntatore stesso deve essere intrinsecamente definita come un offset negativo del puntatore dello stack.

Memorizzazione dell'indirizzo al telaio del chiamante [ modifica ]

Nella maggior parte dei sistemi un fotogramma di stack ha un campo per contenere il valore precedente del registro puntatore frame, il valore che aveva durante l'esecuzione del chiamante. Ad esempio, il frame dello stack di DrawLine avrebbe una posizione di memoria che detiene il valore del puntatore di frame utilizzato da DrawSquare (non mostrato nel diagramma sopra). Il valore viene salvato all'ingresso alla subroutine e ripristinato al ritorno. Avere tale campo in una posizione conosciuta nel frame della pila consente al codice di accedere a ciascun fotogramma successivamente sotto la struttura del routine attualmente in esecuzione e consente anche alla routine di ripristinare facilmente il puntatore del fotogramma sul telaio del chiamante , proprio prima che ritorni.

Routine di nidificazione lessicale [ modifica ]

Ulteriori informazioni: Funzione nidificata e variabile non locale

Le lingue di programmazione che supportano le sottoprogrammi nidificate hanno anche un campo nel riquadro di chiamata che indica la struttura dello stack dell'ultima attivazione della procedura che più chiaramente incapsula la callee, vale a dire l' ambito immediato della callee. Questo è chiamato un collegamento di accesso o un collegamento statico (in quanto tiene traccia di un nesting statico durante le chiamate dinamiche e ricorsive) e fornisce la routine (e tutte le altre routine che può invocare) l'accesso ai dati locali delle sue routine incapsulanti ad ogni nesting livello. Alcune architetture, compilatori o casi di ottimizzazione memorizzano un collegamento per ogni livello di chiusura (non solo l'immediatamente racchiuso), in modo che le routine profondamente nidificate che accedano a dati poco profondi non devono attraversare diversi collegamenti; Questa strategia viene spesso chiamata "display". [3]

I collegamenti di accesso possono essere ottimizzati quando una funzione interna non accede ad alcun dato locale (non costante) nell'incapsulamento, come nel caso delle funzioni pura che comunicano solo per argomenti e valori di ritorno, ad esempio. Alcuni computer storici, come i grandi sistemi Burroughs , avevano "registri di visualizzazione" speciali per supportare le funzioni nidificate, mentre i compilatori per le macchine più moderne (come l'ubiquit x86) semplicemente riservano qualche parola sulla pila per i puntatori, se necessario.

Sovrapposizione [ modifica ]

Per alcuni scopi, la struttura dello stack di una subroutine e quella del suo chiamante può essere considerata sovrapposta, la sovrapposizione consistente nell'area in cui i parametri vengono passati dal chiamante alla callee. In alcuni ambienti, il chiamante spinge ogni argomento sullo stack, estendendo così il suo frame di pile e invoca la callee. In altri ambienti, il chiamante dispone di un'area preallocata nella parte superiore del suo frame di pile per contenere gli argomenti forniti ad altre sottoprogrammi che chiama. Questa zona è a volte denominata area di argomenti in uscita o area di chiamata . Sotto questo approccio, la dimensione dell'area viene calcolata dal compilatore per essere il più grande necessario da qualsiasi subroutine chiamata.

Usa [ modifica ]

Elaborazione del sito di chiamata [ modifica ]

Di solito la manipolazione delle stazioni di chiamata necessarie al sito di una chiamata a una subroutine è minima (che è buono in quanto non ci possono essere molti siti di chiamata per ciascuna sottoprogramma da chiamare). I valori per gli argomenti effettivi vengono valutati al sito di chiamata, in quanto sono specifici per la chiamata particolare e vengono spinti sulla pila o inseriti nei registri, come determinato dalla convenzione di chiamata utilizzata. L'istruzione di chiamata effettiva, ad esempio "ramo e collegamento", viene quindi tipicamente eseguita per trasferire il controllo sul codice della subroutine di destinazione.

Elaborazione delle sottoroute [ modifica ]

Nella subroutine chiamata, il primo codice eseguito viene solitamente chiamato il prologo di sottoprogramma , poiché fa la necessaria pulizia prima che il codice per le dichiarazioni della routine sia iniziato.

Il prologo salva generalmente l'indirizzo di ritorno lasciato in un registro dall'istruzione di chiamata spingendo il valore sullo stack di chiamata. Analogamente, è possibile spingere i puntatori e / o i puntatori del frame. In alternativa, alcune architetture di set di istruzioni forniscono automaticamente funzionalità paragonabili come parte dell'azione dell'istruzione di chiamata stessa e in un tale ambiente il prologo non deve farlo.

Se vengono utilizzati puntatori di frame, il prologo imposta tipicamente il nuovo valore del registro del puntatore di frame dal puntatore dello stack. Spazio nello stack per le variabili locali può essere assegnato modificando in modo incrementale il puntatore dello stack.

Il linguaggio di programmazione Forth consente l'avvio esplicito dello stack di chiamata (chiamato lì "stack di ritorno").

Processo di restituzione [ modifica ]

Quando una subroutine è pronta a tornare, esegue un'epilogo che annulla le fasi del prologo. Questo ripristina tipicamente i valori di registro salvati (ad esempio il valore del puntatore di fotogramma) dal fotogramma dello stack, elimina l'intero frame dello stack dalla stack modificando il valore del puntatore dello stack e, infine, si associa all'istruzione all'indirizzo di ritorno. In numerose convenzioni di chiamata, gli elementi spuntati dalla pila dall'epilogo includono i valori di argomento originali, nel qual caso non esistono più manipolazioni di stack che devono essere eseguite dal chiamante. Con alcune convenzioni di chiamata, tuttavia, è la responsabilità del chiamante di rimuovere gli argomenti dalla pila dopo il ritorno.

Srotolamento [ modifica ]

Tornando dalla funzione chiamata, verrà disattivato il frame superiore dello stack, magari lasciando un valore restituito. L'atto più generale di sbloccare uno o più fotogrammi fuori dalla pila per riprendere l'esecuzione altrove nel programma viene chiamato lo svolgimento dello stack e deve essere eseguito quando vengono utilizzate strutture di controllo non locali, come quelle utilizzate per la gestione delle eccezioni . In questo caso, il frame dello stack di una funzione contiene una o più voci che specifica gestori di eccezioni. Quando viene generata un'eccezione, lo stack viene srotolato finché non viene trovato un gestore che è pronto a gestire (cattura) il tipo di eccezione lanciata.

Alcune lingue dispongono di altre strutture di controllo che richiedono un svolgimento generale. Pascal consente ad un'istruzione globale goto di trasferire il controllo da una funzione annidata e in una funzione esterna precedentemente invocata. Questa operazione richiede che lo stack venga svitato, rimuovendo il numero di fotogrammi di stack necessari per ripristinare il contesto appropriato per trasferire il controllo all'istruzione di destinazione all'interno della funzione esterna di chiusura. Analogamente, C ha le funzioni longjmp e longjmp che fungono da gotos non locali. Il comune Lisp consente di controllare cosa succede quando la pila viene sganciata utilizzando l'operatore speciale per la unwind-protect antiappannamento.

Quando si applica una continuazione , lo stack è (logicamente) svolto e poi riavvolto con lo stack della continuazione. Questo non è l'unico modo per implementare le continue; Per esempio, utilizzando pile multiple esplicite, l'applicazione di una continuazione può semplicemente attivare la sua pila e vento di un valore da passare. Il linguaggio di programmazione di Scheme consente di eseguire funge arbitrarie in punti specifici su "svolgimento" o "riavvolgimento" dello stack di controllo quando viene invocata una continuazione.

Ispezione [ modifica ]

Vedere anche: Profilatura (programmazione computerizzata)

A volte lo stack di chiamate può essere ispezionato mentre il programma è in esecuzione. A seconda di come viene scritto e compilato il programma, è possibile utilizzare le informazioni sulla stack per determinare i valori intermedi e le tracce delle chiamate di funzione. Questo è stato utilizzato per generare test automatizzati a grana fine [4] e in casi come Ruby e Smalltalk, per implementare continuazioni di prima classe. Ad esempio, il GNU Debugger (GDB) implementa l'ispezione interattiva dello stack di chiamata di un programma in esecuzione, ma in pausa, C. [5]

Prendere campioni di tempo regolari dello stack di chiamata può essere utile per profilare le prestazioni dei programmi, poiché se un puntatore di sottoprogramma viene visualizzato molte volte sui dati di campionamento delle stazioni di chiamata, è probabile che si verifichi un collo di bottiglia e dovrebbe essere ispezionato per problemi di prestazioni.

Sicurezza [ modifica ]

Articolo principale: overflow del buffer di stack

In una lingua con puntatori gratuiti o scritture di array non controllate (ad esempio in C), la miscelazione di dati di flusso di controllo che influenza l'esecuzione del codice (gli indirizzi di ritorno o i puntatori di frame salvati) ei dati di programma semplici (parametri o valori di ritorno ) In una call stack è un rischio di sicurezza, probabilmente sfruttabile attraverso i buffer overflow dello stack come il tipo più comune di buffer overflow .

Uno di questi attacchi comporta la compilazione di un buffer con codice eseguibile arbitrario e quindi traboccante dello stesso buffer o di un altro buffer per sovrascrivere un indirizzo di ritorno con un valore che punta direttamente al codice eseguibile. Di conseguenza, quando la funzione restituisce, il computer esegue tale codice. Questo tipo di attacco può essere facilmente bloccato con W ^ X. [ Citazione necessaria ] Gli attacchi simili possono avere successo anche con la protezione W ^ X abilitata, incluso l' attacco return-to-libc o gli attacchi provenienti dalla programmazione orientata al ritorno . Sono state proposte varie mitigazioni, come l'archiviazione di array in una posizione completamente separata dalla riga di ritorno, come nel linguaggio di programmazione Forth. [6]