Dom > Razstava > Vsebine

Prikazni register ali podatkovna struktura za lociranje okvirov stožca ugnezdenih funkcij v računalniškem programiranju

Apr 22, 2017

Klic pokliči

V računalniških znanjih je skupek klicev podatkovna struktura skladov, ki hrani podatke o aktivnih podprogramih računalniškega programa . Ta vrsta skladov je znana tudi kot izvedbeni sklad , programski sveženj , kontrolni sklad , časovni potek časa ali stack stroj in se pogosto skrajša samo na "sklad". Čeprav je vzdrževanje klicnega naklada pomembno za pravilno delovanje večine programske opreme , so podrobnosti navadno skrite in avtomatične v programskih jezikih na visoki ravni . Veliko računalniških navodil določa posebna navodila za manipulacijo z nizi.

Klicni naboj se uporablja za več sorodnih namenov, vendar je glavni razlog za to, da sledimo točki, na katero mora vsak aktivni podprogram vrniti nadzor, ko konča izvršitev. Aktivna podprograma je tista, ki je bila klicana, vendar še ni zaključena, po kateri je treba vrniti kontrolno točko. Takšna aktivacija podprogramov je lahko ugnezdena na katero koli stopnjo (rekurzivna kot poseben primer), zato je struktura skladov. Če na primer podprogram DrawSquare pokliče podprogram DrawLine iz štirih različnih krajev, mora DrawLine vedeti, kje se vrne, ko se njegovo izvedbo konča. Da bi to dosegli, je naslov za klicni ukaz , povratni naslov , vsak klic potisnjen v ogrodje klicev.


Vsebina

[ Skrij ]


Opis [ uredi ]

Ker je stavek klicov organiziran kot sklad , klicatelj vrne povratni naslov na snop in pokliči, ko konča, povleče ali popušča povratni naslov iz ogrodja klicev in prenese nadzor na ta naslov. Če imenovani podprogram kliče še eno podprogram, bo na stavek klicev pritiskal še en povratni naslov in tako naprej, pri čemer se bodo informacije nalagale in odzvale, ko program to narekuje. Če potiskanje porabi ves prostor, dodeljen za sveženj klicev, pride do napake, ki se imenuje preliv skladov , kar na splošno povzroči, da se program zruši . Dodajanje vnosa podprograma v skupek klicev se včasih imenuje "navijanje"; Nasprotno, odstranjevanje vnosov je "odvijanje".

Običajno je natanko en stenski zvezek, povezan s tekočim programom (ali natančneje, z vsako nalogo ali nitjo procesa ), čeprav se lahko ustvarijo dodatni nizi za obdelavo signalov ali sodelovalno večopravilnost (kot pri setcontext ). Ker je v tem pomembnem kontekstu samo ena, jo lahko označimo kot sklad (implicitno, "naloge"); Vendar je v programskem jeziku Forth v podatkovnem svežnju ali stiskalniku parametrov bolj eksplicitno dostopen od snopa klicev in se običajno imenuje sklad (glej spodaj).

V programskih jezikih na visoki ravni so posebnosti stičišča klicev ponavadi skrite od programerja. Dostopajo jim le do niza funkcij, ne pa tudi pomnilnika v samem naboru. To je primer odvzema . Večina jezikov za sestavljanje , na drugi strani, zahteva, da programerji sodelujejo pri manipuliranju s skladom. Dejanski podatki o skladu v programskem jeziku so odvisni od prevajalnika , operacijskega sistema in razpoložljivega nabor navodil .

Funkcije klicnega sklada [ uredi ]

Kot je že omenjeno, je glavni namen klicnega vira shranjevanje povratnih naslovov . Ko se pokliče podprogram, je treba mesto (naslov) ukaza, na katerem se lahko kasneje nadaljuje, nekje shraniti. Uporaba sklada za shranjevanje povratnega naslova ima pomembne prednosti pred alternativnimi klicnimi konvencijami . Eden je, da ima vsaka naloga svoj lastni kup, zato se podprogram lahko ponavlja , torej je lahko hkrati dejaven za različne naloge, ki počnejo različne stvari. Druga prednost je, da se rekurzija samodejno podpira. Ko se funkcija samodejno klici rekurzivno, je treba za vsako aktivacijo funkcije shraniti povratni naslov, tako da ga lahko kasneje uporabite za vrnitev iz aktivacije funkcije. Strukture stikov omogočajo to zmožnost samodejno.

Odvisno od jezika, operacijskega sistema in strojnega okolja lahko ogrodje klicev služi dodatnim namenom, vključno na primer:

Lokalno shranjevanje podatkov


Podprogram pogosto potrebuje pomnilniški prostor za shranjevanje vrednosti lokalnih spremenljivk , spremenljivk, ki so znane le v aktivni podprogram in ne ohranijo vrednosti po vrnitvi. Pogosto je primerna dodelitev prostora za to uporabo tako, da preprosto premaknete zgornji del svežnja z dovolj prostora, da zagotovite prostor. To je zelo hitro v primerjavi z dinamičnim dodeljevanjem pomnilnika , ki uporablja prostor kup . Upoštevajte, da vsaka ločena aktivacija podprograma za lokalno prebivalstvo dobi svoj ločen prostor v kupu.


Prehod parametrov


Podprogrami pogosto zahtevajo, da se vrednosti za parametre priskrbijo s kodo, ki jih kliče, in ni nič nenavadnega, da je prostor za te parametre lahko določen v kupnem paketu. Na splošno, če obstaja le nekaj majhnih parametrov, se za prenose vrednosti uporabijo registri procesorjev , če pa je več parametrov, ki jih je mogoče obravnavati, bo potreben pomnilniški prostor. Sestav klicov deluje dobro kot mesto za te parametre, zlasti ker bo vsak poziv k podprogramu, ki ima različne parametre, v tem paketu dodeljen ločen prostor v skupnem razredu.


Ocenjevalni sklad


Obrati za aritmetične ali logične operacije se najpogosteje dajo v registre in delujejo tam. Vendar pa se lahko v nekaterih situacijah operandi zlagajo do poljubne globine, kar pomeni, da je treba uporabiti nekaj več kot registri (to velja za razlitje registra ). Snop takšnih operandov, podobno kot v računalniku RPN , se imenuje ocenjevalni sveženj in lahko zasede prostor v kupu klicev.


Kazalec na trenutni primer


Nekateri objektno usmerjeni jeziki (npr. C + + ) hranijo ta kazalec skupaj z argumenti funkcij v svežnju klicev pri klicanju metod. Ta kazalec opozarja na primerek objekta, povezan z metodo, ki jo želite uporabiti.


Vključitev podprogramskega konteksta


Nekateri programski jeziki (npr. Pascal in Ada ) podpirajo izjavo ugnezdenih podprogramov , ki jim je dovoljeno dostopati do konteksta njihovih obkolnih rutin, tj. Parametrov in lokalnih spremenljivk v okviru zunanjih podprogramov. Tako statično gnezdenje se lahko ponovi - funkcija, deklarirana znotraj funkcije, ki je razglašena znotraj funkcije ... Izvedba mora zagotoviti način, s katerim lahko imenovana funkcija na katerikoli statični ravni gnezdenja sklicuje na obodni okvir na vsakem zaprtem nivoju gnezdenja. Navadno se to sklicevanje izvaja s kazalcem na okvir zadnjega aktiviranega primera omejevalne funkcije, ki se imenuje "povezava spodaj" ali "statična povezava", da se razlikuje od "dinamične povezave", ki se nanaša na neposrednega klicatelja ( Ki ni nujno statična matična funkcija).


Namesto statične povezave se lahko sklicevanja na zaprtje statičnih okvirov zbirajo v niz kazalnikov, znanih kot prikaz, ki je indeksiran, da poišče želeni okvir. Globina rutinskega leksičnega gnezdenja je znana konstanta, zato je velikost rutinega prikaza fiksna. Tudi število znakov, ki vsebujejo tok, je znano, določen je tudi indeks v prikazu. Običajno se rutinski zaslon nahaja v svojem okvirom stacka , vendar je Burroughs B6500 izvedel tak zaslon v strojni opremi, ki je podpirala do 32 stopenj statičnega gnezdenja.


Prikazovalni vpisi, ki vsebujejo obsege, so pridobljeni iz ustrezne predponke prikazovalnika klicatelja. Notranja rutina, ki ponavlja, ustvarja ločene okvire klicev za vsako klicanje. V tem primeru vse statične povezave znotraj notranje rutine kažejo na isti zunanji rutinski kontekst.


Drugo stanje vrnitve


Poleg povratnega naslova lahko v nekaterih okoljih obstajajo tudi druga stanja naprav ali programske opreme, ki jih je treba obnoviti, ko se podomot se vrne. To lahko vključuje stvari, kot so raven privilegijev, informacije o ravnanju z izjemo, aritmetične načine in tako naprej. Če je potrebno, se lahko to shranjuje v klicih tako, kot je naslov za povratni klic.


Tipični klicni stavek se uporablja za povratni naslov, domačine in parametre (znano kot okvir klica ). V nekaterih okoljih je morda več ali manj funkcij, dodeljenih klicu. V programskem jeziku Forth , na primer ponavadi samo povratni naslov, štejejo parametre in indikatorje zanke ter morebitne lokalne spremenljivke, shranjene v skupnem razredu (ki je v tem okolju označeno kot povratni paket ), čeprav je mogoče začasno postaviti vse podatke Tam uporablja posebno kodo za vračanje kupona, dokler se upoštevajo potrebe klicev in donosov; Parametri se običajno shranijo v ločeni podatkovni sveženj ali stack parametra , ki se ponavadi imenuje stavek v terminologiji Forth, čeprav je stevilka klicev, ker je navadno dostopnejša bolj eksplicitno. Nekateri Forthi imajo tudi tretji kup za parametre s plavajočo vejico .

Struktura [ uredi ]

Postavitev stikov klicev

Klicni sklop je sestavljen iz okvirov stev (imenovanih tudi aktivacijskih zapisov ali okvirov za aktiviranje ). To so strojno odvisne in ABI- odvisne podatkovne strukture, ki vsebujejo podatke o podprogramu. Ti podatki se včasih imenujejo CFI (Call Frame Information). [1] Vsak okvir sklada ustreza klicu podprogramu, ki še ni končan s povratkom. Na primer, če se podprogram z imenom DrawLine trenutno izvaja, ko je bil pozvan s podprogramom DrawSquare , je lahko zgornji del DrawSquare klica postavljen kot na sliki na desni.

Diagram, kot je ta, lahko potegnemo v obe smeri, dokler se razume postavitev zgornjega in tako smer gibanja kupov. Poleg tega se neodvisno od tega arhitekture razlikujejo glede na to, ali klicni nizi rastejo proti višjim naslovom ali na nižje naslove. Logika diagrama je neodvisna od izbire naslova.

Okvir s skladom na vrhu snopa je za trenutno opravilno rutino. Okvir kupa običajno vključuje vsaj naslednje elemente (v naročilu za potiskanje):

  • Argumenti (vrednosti parametrov) so bili posredovani rutini (če obstajajo);

  • Povratni naslov nazaj na klicatelja podprograma (npr. V okvirju DrawLine , naslov v kodo DrawSquare ); In

  • Prostor za lokalne spremenljivke rutine (če obstaja).

Stack in okvirji kazalcev [ uredi ]

Kadar se velikost okvirja lahko razlikuje, na primer med različnimi funkcijami ali med klicanjem določene funkcije, popping okvirja iz svežnja ne predstavlja fiksnega zmanjšanja kazalca sklada . Pri vrnitvi funkcije se namesto kazalke povrne v kazalec okvirja , vrednost indikatorja sklada neposredno pred klicem funkcije. Vsak od obeh okvirjev vsebuje kazalec na zgornji del okvirja, ki je takoj spodaj. Kazalec snopa je spremenljiv register, ki je deljen med vsemi pozivi. Kazalec okvirja za dano pozivanje funkcije je kopija kazalca zlaganja, kakršna je bila pred aktiviranjem funkcije. [2]

Lokacije vseh drugih polj v okviru se lahko določijo relativno bodisi na vrhu okvira kot negativne izravnave kazalca steze ali glede na zgornji del okvirja spodaj kot pozitivna izravnava kazalca okvirja. Mesto kazalca okvirja mora biti sama po sebi opredeljeno kot negativen odmik kazalca sklada.

Shranjevanje naslova v okvir klicatelja [ uredi ]

V večini sistemov ima okvir stevca, ki vsebuje prejšnjo vrednost kazalnega registra okvirja, vrednost, ki jo je imela med izvajanjem klicatelja. Na primer, okvir DrawLine bi imel lokacijo pomnilnika, ki drži vrednost kazalca, ki jo DrawSquare uporablja (ni prikazana na zgornjem diagramu). Vrednost se shrani ob vnosu v podprogram in se ob vrnitvi vrne. Ob takem polju na znanem mestu v okvirnem okvirju omogoča, da koda zaporedoma dostopa do vsakega okvira pod okvirjem trenutne izvršilne rutine, in omogoča rutino, da enostavno povrne kazalec okvirja v okvir klicatelja , tik preden se vrne.

Lexično ugnešene rutine [ uredi ]

Dodatne informacije: Vgnezdena funkcija in Ne-lokalna spremenljivka

Programski jeziki, ki podpirajo ugnezdene podprograme, imajo tudi polje v klicnem okvirju, ki kaže na okvir stacka najnovejše aktivacije postopka, ki najbolj zaokroži naključno, tj. Neposredni obseg žetona. To se imenuje povezava za dostop ali statična povezava (saj spremlja statično gnezdenje med dinamičnimi in rekurzijskimi klici) in zagotavlja rutino (in tudi druge rutine, ki jih lahko uveljavlja) dostop do lokalnih podatkov o svojih encapsulativnih rutinah pri vsakem ugneženju Ravni. Nekatere arhitekture, prevajalniki ali primeri optimizacije shranjujejo eno povezavo za vsako stopnjo zaprtja (ne le neposredno obdajajo), tako da globoko ugnezdene podprograme, ki imajo dostop do plitkih podatkov, ne smejo preiti več povezav; Ta strategija se pogosto imenuje "prikaz". [3]

Dostopne povezave se lahko optimizirajo, ko notranja funkcija ne more dostopati do (ne-konstantnih) lokalnih podatkov v enkapsulaciji, kot v primeru čistih funkcij, ki komunicirajo le z argumenti in povratnimi vrednostmi. Nekateri zgodovinski računalniki, kot so veliki sistemi Burroughs , so imeli posebne "prikazne registre" za podporo ugnezdenih funkcij, medtem ko so prevajalniki za večino sodobnih naprav (kot je povsod x86) preprosto rezerviral nekaj besed v kupu za kazalnike, kot je bilo potrebno.

Prekrivanje [ uredi ]

Za nekatere namene se lahko šteje, da se okvir sklada podprograma in njegovega klicatelja prekrivata, prekrivanje pa obsega območje, kjer se parametri prenesejo od kličočega na pozivnika. V nekaterih okoljih klicatelj vsakega argumenta potisne v sveženj, s čimer podaljša svoj okvir skladov, nato pa kliče zaljubljenca. V drugih okoljih ima klicatelj predodeljeno območje na vrhu okvira stev, ki drži argumente, ki jih dobavlja drugim podprogramom, ki jih kliče. To območje včasih imenujemo območje odhodnih argumentov ali območje oblačka . V skladu s tem pristopom je velikost območja izračunana s strani prevajalnika, ki je največja, potrebna za vsako imenovano podprogram.

Uporabi [ uredi ]

Obdelava klicne strani [ uredi ]

Običajno je manipulacija s strežniškim številom klicev, ki je potrebna na mestu klica v podprogram, minimalna (kar je dobro, saj lahko za vsako podprogramsko številko pozovete številna mesta klicev). Vrednosti za dejanske argumente se ocenjujejo na mestu klica, saj so specifične za določen klic in so bodisi potisnjene v snop ali v registre, kot to določa uporabljena konvencija . Dejansko izvedeno klicno navodilo, na primer "podružnica in povezava", se običajno izvede, da prenese nadzor na kodo ciljne podprogramov.

Obdelava vnosa podprogramov [ uredi ]

V imenovanem podprogramu se prva izvedena koda ponavadi imenuje podprogramski podprogram , ker opravi potrebno gospodinjstvo pred začetkom kode za izjave rutine.

Prolog bo običajno shranil vrnjeni naslov v registru z ukazom za klic tako, da bo vrednost potisnila v sveženj klicev. Podobno lahko pritisnete trenutno trenutni kazalec in / ali vrednosti kazalca. Druga možnost je, da nekatere arhitekture nabor navodil samodejno zagotovijo primerljivo funkcionalnost kot del ukrepa samega klicnega ukaza, v takem okolju pa temu prologu ni treba storiti.

Če se uporabljajo kazalnike okvirja, bo prolog običajno nastavil novo vrednost kazalnika kazalnikov okvirja iz kazalca. Prostor v skladu za lokalne spremenljivke se nato lahko dodeli s postopnim spreminjanjem kazalca.

Programski jezik Forth omogoča eksplicitno navijanje sklada klicev (imenovan je "povratni paket").

Obdelava vračila [ uredi ]

Ko je podprogram pripravljen za vrnitev, izvede epilog, ki razveljavi korake prologa. To bo ponavadi obnavljalo shranjene vrednosti registra (na primer vrednost kazalca kazalca) iz okvira stev, poprodati celotni okvir stacka iz svežnja s spremembo vrednosti kazalca stema in se na koncu vrniti na ukaz na povratnem naslovu. V skladu s številnimi klicnimi konvencijami so elementi, ki jih je epilog spustil iz kupa, vključevali izvirne vrednosti argumentov, pri čemer običajno ni nadaljnjih manipulacij, ki jih mora klicatelj opraviti. Z nekaterimi klicnimi konvencijami pa je klicatelj dolžan odstraniti argumente iz kupa po vrnitvi.

Razveljavitev [ uredi ]

Če se vrnete iz klicane funkcije, se zgornji okvir izklopi iz svežnja, morda bo zapustil povratno vrednost. Bolj splošen čin popping enega ali več okvirov izven svežnja, da se nadaljuje izvajanje drugje v programu, se imenuje preoblikovanje sklada in ga je treba izvesti, ko se uporabijo ne-lokalne strukture nadzora, kot so tiste, ki se uporabljajo za ravnanje z izjemami . V tem primeru okvir stevca funkcije vsebuje enega ali več vnosov, ki opredeljujejo obdelovalce izjeme. Ko se izjeme vržejo, se kup odvija, dokler se ne najde upravljalnik, ki je pripravljen za obdelavo (ulov) vrste izpuščene izjeme.

Nekateri jeziki imajo druge strukture nadzora, ki zahtevajo splošno odvijanje. Pascal omogoča globalno goto izjavo, da prenese nadzor iz ugnezdene funkcije in v predhodno uveljavljeno zunanjo funkcijo. Za to operacijo je potrebno, da se sveženj odvrže, odstranite toliko okvirov stev, kot je potrebno, da obnovite ustrezen kontekst, da prenesete nadzor na ciljni izpis v zunanji zunanji funkciji. Podobno ima C tudi funkcije setjmp in longjmp ki delujejo kot ne-lokalni gotos. Common Lisp omogoča nadzor nad tem, kaj se zgodi, ko se kup odvije z uporabo posebnega operaterja, ki se odzove.

Pri uporabi nadaljevanja je sklad (logično) odvit in nato ponovno prepleten s svežnjem nadaljevanja. To ni edini način za izvajanje nadaljevanj; Na primer z uporabo večkratnih, eksplicitnih nizov, lahko uporaba nadaljevanja preprosto aktivira svoj sveženj in prinese vrednost, ki jo je treba prenesti. Programski jezik sheme omogoča, da se v določenih točkah izvajajo poljubne tanke pri "odvijanju" ali "previjanju" kontrolnega svežnja, kadar se sproži nadaljevanje.

Pregled [ uredi ]

Glej tudi: Profiliranje (računalniško programiranje)

Kadar program deluje, lahko včasih pregledujete skupek klicev. Odvisno od tega, kako je program napisan in preveden, se lahko informacije o skladih uporabijo za določitev vmesnih vrednosti in sledi klicev funkcij. To je bilo uporabljeno za ustvarjanje fino zrnatih avtomatiziranih testov, [4] in v primerih, kot sta Ruby in Smalltalk, za izvajanje prvovrstnih nadaljevanj. Kot primer, GNU Debugger (GDB) izvaja interaktivni pregled stisknega klica tekočega, a zaustavljenega programa C. [5]

Če vzamete vzorce rednega časa v skupek klicev, je lahko uporabno pri profiliranju uspešnosti programov, ker če je kazalec podmutiča večkrat prikazan v podatkovnih zbirkah zbirke klicev, je verjetno ozek grlo kode in ga je treba pregledati pri težavah z zmogljivostjo.

Varnost [ uredi ]

Glavni članek: Overflow buffer

V jeziku z brezplačnimi kazalci ali zapisi, ki niso označeni v matriki (kot je v C), je mešanje podatkov nadzornega toka, ki vplivajo na izvajanje kode (povratni naslovi ali shranjeni kazalniki okvirja) in preprosti programski podatki (parametri ali povratne vrednosti ) V ogrodju klicev je varnostno tveganje, ki se lahko zgodi, da se prek prelitkov stednega vmesnika uporabi kot najpogostejša vrsta presežkov medpomnilnika .

Eden od takih napadov je izpolnjevanje enega vmesnega pomnilnika z poljubno izvedljivo kodo in nato prelivanje istega ali kakšnega drugega vmesnega pomnilnika za prepisovanje nekaterih povratnih naslovov z vrednostjo, ki neposredno označuje izvedljivo kodo. Ko se funkcija vrne, računalnik to kodo izvede. Takšno napako je mogoče zlahka blokirati z W ^ X. Podobni napadi so lahko uspešni tudi z omogočeno zaščito W ^ X, vključno z napadom vračanja v libc ali napadom, ki prihajajo iz programov, usmerjenih v vračanje . Predlagane so bile različne omilitve, kot so shranjevanje nizov na povsem ločeni lokaciji iz povratnega nabora, kot je to v programskem jeziku Forth. [6]