Casa > Exposició > Contingut

Mostra el registre o l'estructura de dades, per localitzar els marcs de pila de funcions nidificades en la programació d'ordinadors

Apr 22, 2017

Pila de trucades

En informàtica , una pila de trucades és una estructura de dades de pila que emmagatzema informació sobre les subrutines actives d'un programa informàtic . Aquest tipus de pila també es coneix com una pila d'execució , pila de programa , pila de control , pila d' execució o pila de màquina , i sovint es redueix a només "la pila". Tot i que el manteniment de la pila de trucades és important per al bon funcionament de la majoria de programari , les dades normalment són ocultes i automàtiques en llenguatges de programació d'alt nivell . Molts conjunts d'instruccions informàtiques proporcionen instruccions especials per a la manipulació de piles.

Una pila de trucades s'utilitza per a diversos propòsits relacionats, però el principal motiu per tenir un és fer un seguiment del punt en què cada subrutina activa hauria de tornar el control quan s'acaba d'executar. Una subrutina activa és una que s'ha anomenat però encara no s'ha completat l'execució després de la qual el control s'hauria de retornar al punt de crida. Aquestes activacions de subrutines es poden anidar a qualsevol nivell (recursiu com a cas especial), d'aquí l'estructura de la pila. Si, per exemple, una subrutina DrawSquare crida a una subrutina DrawLine de quatre llocs diferents, DrawLine ha de saber a on tornar quan finalitza la seva execució. Per aconseguir-ho, l' adreça següent a la instrucció de trucada, l' adreça de retorn , es porta a la pila de trucades amb cada trucada.


Continguts

[ Amaga ]


Descripció [ edita ]

Atès que la pila de trucades s'organitza com una pila , la persona que truca empeny l'adreça de retorn a la pila, i la subrutina anomenada, quan finalitza, treu o apareix l'adreça de retorn de la pila de trucades i transfereix el control a aquesta adreça. Si una subrutina anomenada convoca una altra subrutina, empenyrà una altra adreça de retorn a la pila de trucades, i així successivament, amb la informació acumulada i desestabilitzadora tal com ho dic el programa. Si l'empenyi consumeix tot l'espai assignat per a la pila de trucades, es produeix un error anomenat desbordament de pila , generalment causant que el programa es bloquegi . Afegint l'entrada d'una subrutina a la pila de trucades de vegades s'anomena "liquidació"; Al contrari, l'eliminació d'entrades és "desenrotllar-se".

Normalment hi ha una sola pila de trucades associada amb un programa en execució (o més precisament, amb cada tasca o cadena d'un procés ), encara que es poden crear piles addicionals per al maneig de senyals o la multitarea cooperativa (com amb el context establert ). Atès que només hi ha un en aquest context important, es pot anomenar la pila (implícitament, "de la tasca"); Tanmateix, en el llenguatge de programació Forth, la pila de dades o la pila de paràmetres s'accedeix de manera més explícita que la pila de trucades i es denomina comunament la pila (vegeu més avall).

En llenguatges de programació d'alt nivell , els detalls de la pila de trucades solen estar amagats del programador. Només se'ls dóna accés a un conjunt de funcions, i no a la memòria de la pila. Aquest és un exemple d' abstracció . La majoria dels llenguatges de muntatge , en canvi, requereixen que els programadors estiguin relacionats amb la manipulació de la pila. Els detalls reals de la pila d'un llenguatge de programació depenen del compilador , del sistema operatiu i del conjunt d'instruccions disponible.

Funcions de la pila de trucades [ edita ]

Com es va assenyalar anteriorment, l'objectiu principal d'una pila de trucades és emmagatzemar les adreces de retorn . Quan s'anomena una subrutina, s'haurà de desar la ubicació (adreça) de la instrucció en la qual es pugui reprendre posteriorment. L'ús d'una pila per guardar l'adreça de retorn té avantatges importants sobre convencions de trucades alternatives. Una d'elles és que cada tasca pot tenir una pila pròpia i, per tant, la subrutina pot ser reentrada , és a dir, pot ser actiu simultàniament per a diferents tasques fent coses diferents. Un altre avantatge és que la recursió és compatible automàticament. Quan una funció es crida de manera recursiva, cal emmagatzemar una adreça de retorn per a cada activació de la funció de manera que es pugui utilitzar posteriorment per tornar de l'activació de la funció. Les estructures de pila proporcionen aquesta capacitat automàticament.

Depenent del idioma, del sistema operatiu i de l'entorn de la màquina, una pila de trucades pot servir fins addicionals, com per exemple:

Emmagatzematge de dades locals


Sovint, una subrutina necessita un espai de memòria per emmagatzemar els valors de les variables locals , les variables que només es coneixen dins de la subrutina activa i no conserven els valors després de la seva devolució. Sovint és convenient assignar espai per a aquest ús simplement movent la part superior de la pila amb prou per proporcionar l'espai. Això és molt ràpid quan es compara amb l'assignació de memòria dinàmica , que utilitza l' espai de pila . Tingueu en compte que cada activació separada d'una subrutina obté el seu propi espai separat a la pila per als habitants locals.


Passant el paràmetre


Sovint, les subrutines requereixen que els valors dels paràmetres els siguin subministrats pel codi que els crida, i no és estrany que l'espai d'aquests paràmetres es pugui establir a la pila de trucades. En general, si només hi ha alguns paràmetres petits, s'utilitzaran registres de processadors per passar els valors, però si hi ha més paràmetres del que es pot manejar d'aquesta manera, l'espai de memòria serà necessari. La pila de trucades funciona bé com un lloc per a aquests paràmetres, especialment perquè cada crida a una subrutina, que tindrà valors diferents per als paràmetres, tindrà un espai separat a la pila de trucades per a aquests valors.


Pila d'avaluació


Els operands per operacions aritmètiques o lògiques es col·loquen amb més freqüència en registres i s'executen allí. Tanmateix, en algunes situacions, els operands poden apilar-se a una profunditat arbitrària, cosa que significa que cal utilitzar-ne més (és el cas d'un registre d'abocament ). La pila d'aquests operands, més aviat així en una calculadora RPN , s'anomena pila d'avaluació, i pot ocupar espai en la pila de trucades.


Punter a la instància actual


Alguns llenguatges orientats a objectes (per exemple, C + + ), emmagatzemen aquest punter juntament amb els arguments de funció a la pila de trucades quan invoquen mètodes. El punter apunta a la instància d' objecte associada al mètode a invocar.


Tancament del context de subrutines


Alguns llenguatges de programació (p.ex., Pascal i Ada ) donen suport a la declaració de subrutines anidadas , que permeten accedir al context de les seves rutines adjuntes, és a dir, els paràmetres i variables locals dins de l'àmbit de les rutines externes. Aquesta nidificació estàtica pot repetir: una funció declarada dins d'una funció declarada dins d'una funció ... La implementació ha de proporcionar un mitjà mitjançant el qual una funció anomenada en qualsevol nivell d'anidament estàtic donat pot fer referència al marc adjunt en cada nivell d'anidament tancat. Comú aquesta referència s'aplica mitjançant un punter al marc de la instància activada més recent de la funció adjunta, anomenada "enllaç de baixada" o "enllaç estàtic", per distingir-lo del "enllaç dinàmic" que fa referència a l'anomenat immediat ( Que no necessiten ser la funció parent estàtica).


En lloc d'un enllaç estàtic, les referències als marcs estàtics que tanquen es poden recollir en una sèrie de punteres conegudes com una pantalla que està indexada per localitzar un marc desitjat. La profunditat de la nidificació lèxica de la rutina és una constant coneguda, de manera que la mida de la visualització d'una rutina es resol. A més, es coneix el nombre d'àmbits que continguin traverses, l'indicador a la pantalla també es resol. Normalment, la visualització d'una rutina es troba en el seu propi quadre de compilació , però el Burroughs B6500 implementa aquesta visualització en el maquinari que suporta fins a 32 nivells d'anidament estàtic.


Les entrades de visualització que denoten els àmbits que continguin s'obtenen del prefix adequat de la visualització de la persona que truca. Una rutina interna que recursitza crea marcs de trucades separats per a cada invocació. En aquest cas, tots els enllaços estàtics de la rutina interna apunten al mateix context de rutina exterior.


Un altre estat de retorn


Al costat de l'adreça de retorn, en alguns entorns, hi pot haver altres estats de màquina o de programari que calgui restaurar quan torneu una subrutina. Això pot incloure elements com el nivell de privilegi, la informació sobre la manipulació d'excepcions, els modes aritmètics, etc. Si és necessari, això es pot emmagatzemar a la pila de trucades tal com és l'adreça de devolució.


La pila de trucades típica s'utilitza per a l'adreça de retorn, locals i paràmetres (conegut com un marc de trucades ). En alguns entorns, hi pot haver més o menys funcions assignades a la pila de trucades. En el llenguatge de programació Forth , per exemple, normalment només l'adreça de retorn, els paràmetres i els índexs de bucle explicats, i possiblement les variables locals, s'emmagatzemen a la pila de trucades (que en aquest entorn es denomina pila de retorn ), tot i que qualsevol dada es pot col·locar temporalment Utilitzant un codi de gestió de devolució especial sempre que es respectin les necessitats de trucades i devolucions; Els paràmetres solen emmagatzemar-se en una pila de dades o una pila de paràmetres separada, generalment anomenada pila en la terminologia Forth, tot i que hi ha una pila de trucades ja que normalment s'accedeix de forma més explícita. Alguns Forths també tenen una tercera pila per als paràmetres de punt flotant .

Estructura [ edita ]

Disseny de la pila de trucades

Una pila de trucades està composta per marcs de pila (també anomenats registres d' activació o marcs d'activació ). Es tracta d'estructures de dades dependents de la màquina i dependents de l' ABI que contenen informació d'estat subrutina. Aquestes dades a vegades es coneix com CFI (Informació de marc de trucades). [1] Cada quadre de pila correspon a una crida a una subrutina que encara no ha acabat amb una devolució. Per exemple, si una subrutina anomenada DrawLine s'està executant actualment, havent estat cridada per una subrutina DrawSquare , la part superior de la pila de trucades es pot definir com a la imatge de la dreta.

Un diagrama com aquest es pot dibuixar en qualsevol direcció, sempre que s'entengui la posició de la part superior, de manera que es comprengui la direcció del creixement de la pila. A més, independentment d'això, les arquitectures difereixen quant a si les apilades creixen cap a adreces més altes o cap a adreces més baixes. La lògica del diagrama és independent de l'elecció de direcció.

El quadre de pila situat a la part superior de la pila és per a la rutina que s'està executant actualment. El quadre de pila sol incloure almenys els elements següents (en ordre de comandes):

  • Els arguments (valors de paràmetres) passen a la rutina (si n'hi ha);

  • L'adreça de retorn a la persona que truca la rutina (p. Ex., En el marc de la pila de DrawLine , una adreça en el codi de DrawSquare ); I

  • Espai per a les variables locals de la rutina (si n'hi ha).

Punters i punters de marcs [ edita ]

Quan les mides de quadres de pila poden diferir, com entre funcions diferents o entre invocacions d'una determinada funció, fer aparèixer un marc de la pila no constitueix una disminució fixa del punter de pila . A la tornada de la funció, el punter de la pila es restaura al punter del marc , el valor del punter de pila just abans de cridar la funció. Cada marc de pila conté un punter de pila a la part superior del marc immediatament inferior. El punter de pila és un registre mutable compartit entre totes les invocacions. Un punter de marc d'una invocació donada d'una funció és una còpia del punter de la pila tal com era abans de la invocació de la funció. [2]

Les ubicacions de tots els altres camps del marc es poden definir relatives tant a la part superior del marc com a compensacions negatives del punter de pila o relatives a la part superior del quadre següent, com a compensacions positives del punter del marc. La ubicació del punter del marc s'ha de definir inherentment com a compensació negativa del punter de la pila.

Emmagatzemant l'adreça al marc del personatge [ edita ]

En la majoria de sistemes, un quadre de pila té un camp que conté el valor anterior del registre del punter del marc, el valor que tenia mentre l'executor estava executant. Per exemple, el quadre de pila de DrawLine tindria una ubicació de memòria amb el valor del punter del marc que DrawSquare usa (no es mostra al diagrama de dalt). El valor es guarda quan s'introdueix a la subrutina i es restaura després del retorn. Tenir aquest camp en una ubicació coneguda en el marc de la pila permet que el codi accedeixi a cada fotograma successivament sota el marc de rutina actualment executant, i també permet que la rutina restauri fàcilment el punter del marc al marc de la persona que truca , just abans que torni.

Rutines annexes lèxicament [ edita ]

Més informació: Funció niada i variable no local

Els llenguatges de programació que admeten les subrutines aniades també tenen un camp en el marc de trucades que apunta al marc de pila de la darrera activació del procediment que més s'encapsula el callee, és a dir, l' abast immediat de la combinació. Es denomina enllaç d'accés o enllaç estàtic (ja que fa un seguiment de l'anàlisi estàtic durant les trucades dinàmiques i recursives) i proporciona la rutina (així com qualsevol altra rutina que pugui invocar) l'accés a les dades locals de les seves rutines encapsulants a totes les nidificants Nivell Algunes arquitectures, compiladors o casos d'optimització emmagatzemen un enllaç per a cada nivell de tancament (no només el tancament immediat), de manera que les rutines profundament anades que accedeixin a dades poc profundes no han de recórrer diversos enllaços; Aquesta estratègia sovint s'anomena "visualització". [3]

Els enllaços d'accés es poden optimitzar quan una funció interna no accedeix a cap dada local (no constant) a l'encapsulat, com passa amb funcions pures que només es comuniquen mitjançant arguments i valors de retorn, per exemple. Alguns ordinadors històrics, com ara els sistemes grans de Burroughs , tenien "registres de visualització" especials per donar suport a les funcions anidadas, mentre que els compiladors per a les màquines més modernes (com ara l'omnipresent x86) només reserven algunes paraules a la pila per als indicadors, segons sigui necessari.

Superposició [ edita ]

Per a alguns propòsits, es pot considerar que el marc de pila d'una subrutina i el de la persona que truca es superposen, la superposició consisteix en la zona on els paràmetres es passen de la persona que truca a la canalització. En alguns entorns, la persona que truca empeny cada argument a la pila, estenent així el seu marc de pila i, a continuació, invoca la lletra. En altres entorns, l'anomenat té una àrea preestablerta a la part superior del quadre de la pila per mantenir els arguments que proporciona a altres subrutines que crida. Aquesta àrea es denomina de vegades l' àrea de arguments sortints o l' àrea de text destacat . Sota aquest enfocament, el compilador calcula la mida de la zona per ser el més gran necessari per qualsevol subrutina anomenada.

Utilitza [ edita ]

Truqui al lloc de processament [ edita ]

Normalment, la crida a la manipulació de pila necessària en el lloc d'una trucada a una subrutina és mínima (que és bona, ja que hi pot haver molts llocs de trucada per a cada subrutina que es truqui). Els valors dels arguments reals s'avaluen al lloc de la trucada, ja que són específics de la trucada en particular, ja que es mouen a la pila o es col·loquen en registres, tal com determina la convenció de trucada utilitzada. La instrucció de trucada real, com ara "branca i enllaç", normalment s'executa per transferir el control al codi de la subrutina de destinació.

Processament d'entrada subrutina [ edita ]

A la subrutina anomenada, el primer codi executat se sol anomenar el pròleg de la subrutina , ja que fa la neteja necessària abans que comenci el codi per a les declaracions de la rutina.

Normalment, el pròleg estalviarà l'adreça de devolució deixada en un registre per mitjà de la instrucció de trucada, tot empenyent el valor a la pila de trucades. De la mateixa manera, es pot emprar el punter de pila actual i / o els valors del punter del marc. Com a alternativa, algunes arquitectures establertes per instruccions proporcionen automàticament una funcionalitat comparable com a part de l'acció de la instrucció de trucades, i en aquest context el pròleg no necessita fer-ho.

Si s'utilitzen punters de marc, el pròleg normalment establirà el nou valor del registre del punter del marc del punter de pila. A continuació, es pot assignar espai a la pila per a variables locals canviant progressivament el punter de pila.

El llenguatge de programació Forth permet un devançament explícit de la pila de trucades (anomenada allà la "pila de retorn").

Tractament de retorns [ edita ]

Quan una subrutina està a punt per tornar, executa un epíleg que desfà els passos del pròleg. Normalment restaurarà els valors del registre guardats (com ara el valor del punter del marc) del quadre de la pila, deixeu anar tot el marc de pila de la pila canviant el valor del punter de la pila i, finalment, s'uneixin a la instrucció a l'adreça de retorn. En virtut de moltes convencions de trucada, els elements que apareixen a la pila mitjançant l'epíleg inclouen els valors de l'argument original, en aquest cas, normalment, no hi ha manipulacions de pila addicionals que ha de fer la persona que truca. Tanmateix, amb algunes convencions de trucades, és responsabilitat de l'autor de retirar els arguments de la pila després de la devolució.

Desbloqueig [ edita ]

Si torna de la funció anomenada, es mostrarà el marc superior de la pila, potser deixant un valor de retorn. L'acte més general de generar un o més fotogrames de la pila per reprendre l'execució en altres llocs del programa es denomina desbloqueig de pila i s'ha de realitzar quan s'utilitzen estructures de control no locals, com les utilitzades per a la manipulació d'excepcions . En aquest cas, el marc de la pila d'una funció conté una o més entrades que especifiquen controladors d'excepcions. Quan es produeix una excepció, la pila es desenrotlla fins que es troba un controlador que està preparat per manejar (capturar) el tipus de la excepció llançada.

Alguns idiomes tenen altres estructures de control que requereixen desenrotllament general. Pascal permet una declaració de goto global per transferir el control d'una funció anidada i en una funció externa invocada prèviament. Aquesta operació requereix que es desenganxa la pila, eliminant tots els marcs de pila que siguin necessaris per restaurar el context adequat per transferir el control a la instrucció objectiu dins de la funció externa inclosa. De la mateixa manera, C té les funcions setjmp i longjmp que actuen com gotos no locals. Common Lisp permet controlar què passa quan es desenvolupa la pila usant l'operador especial de unwind-protect desenrotllament.

Quan s'aplica una continuació , la pila es (lògicament) es desenrotlla i es tornarà a col·locar amb la pila de la continuació. Aquesta no és l'única manera d'implementar continuacions; Per exemple, utilitzant piles múltiples i explícites, l'aplicació d'una continuació pot simplement activar la seva pila i arrossegar un valor per passar. El llenguatge de programació d'esquemes permet executar trossos arbitraris en punts específics sobre "desenrotllament" o "rebobinat" de la pila de control quan s'invoca una continuació.

Inspecció [ edita ]

Vegeu també: perfils (programació d'ordinadors)

La pila de trucades a vegades pot ser inspeccionada a mesura que s'està executant el programa. Depenent de com s'escriu i compileu el programa, la informació de la pila es pot utilitzar per determinar els valors intermedis i els rastres de trucades de funció. Això s'ha utilitzat per generar proves automatitzades de gra fi [4], i en casos com Ruby i Smalltalk, per implementar les continuacions de primera classe. Com a exemple, GNU Debugger (GDB) implementa la inspecció interactiva de la pila de trucades d'un programa C executable però en pausa. [5]

Fer mostres de temps regular de la pila de trucades pot ser útil per perfilar el rendiment dels programes, ja que si apareix el punter de la subrutina a les dades de mostreig de la pila de trucades moltes vegades, és probable que sigui un coll d'ampolla de codi i que cal inspeccionar per problemes de rendiment.

Seguretat [ edita ]

Article principal: Desbordament de memòria intermèdia de stack

En un idioma amb indicadors gratuïts o matriculacions no verificades (com en C), la barreja de dades de flux de control que afecta l'execució del codi (les adreces de retorn o els indicadors de marcs desats) i les dades del programa senzilles (paràmetres o valors de retorn ) En una pila de trucades és un risc de seguretat, possiblement explotable a través dels desbordaments de memòria intermèdia de la pila, ja que el tipus més comú de desbordament de memòria intermèdia .

Un d'aquests atacs consisteix a omplir un buffer amb un codi executable arbitrari, i després desbordar el mateix buffer o un altre per sobreescriure una adreça de retorn amb un valor que apunta directament al codi executable. Com a resultat, quan la funció torna, l'ordinador executa aquest codi. Aquest tipus d'atac pot ser fàcilment bloquejat amb W ^ X. [ Citació necessària ] Els atacs similars poden tenir èxit fins i tot amb la protecció W ^ X activada, incloent l' atac de retorn a lliura o els atacs derivats de la programació orientada a la devolució . S'han proposat diverses mitigacions, com ara l'emmagatzematge de matrius en una ubicació completament separada de la pila de retorn, com és el cas del llenguatge de programació Forth. [6]