Dom > Izložba > Sadržaj

Prikaz registra ili struktura podataka, za lociranje okvira umetnutih funkcija u računalno programiranje

Apr 22, 2017

Stupac poziva

U računalnoj znanosti , pozivni stog je struktura podataka stanja koja pohranjuje informacije o aktivnim podprogramima računalnog programa . Ova vrsta stoga također je poznata kao izvršni stog , programski stog , kontrolni stog , stablo za vrijeme izvođenja ili strojni stog , a često se skraćuje samo za "stog". Iako je održavanje pozivnog sloga važno za pravilno funkcioniranje većine softvera , detalji su obično skriveni i automatski u programskim jezicima visoke razine . Mnogi kompleti za poučavanje računala pružaju posebne upute za manipuliranje gomilama.

Niz poziva koristi se za nekoliko srodnih ciljeva, ali glavni razlog za to je da prati točku na koju će svaka aktivna podprogram mora vratiti kontrolu kada završi izvršavanje. Aktivni potprogram je onaj koji je pozvan, ali tek treba dovršiti izvršenje, nakon čega bi se kontrola trebala vratiti do točke poziva. Takve aktivacije subroutina mogu biti ugniježđene na bilo koju razinu (rekurzivno kao poseban slučaj), stoga struktura stogova. Ako, na primjer, podprogramme DrawSquare nazove DrawLine iz četiri različita mjesta, DrawLine mora znati gdje se vrati kada izvršenje završi. Da bi se to postiglo, svaki poziv gura poziv na poziv, adresa koja slijedi nakon upućivanja poziva, povratna adresa .


Sadržaj

[ Sakrij ]


Opis [ uredi ]

Budući da je pozivni stalak organiziran kao stog , pozivatelj gura povratnu adresu na stog, a pozvani potprogram, kada završi, povlači ili zakreće povratnu adresu iz stanja poziva i prenosi kontrolu na tu adresu. Ako pozvani podprogram pokrene još jedan potprogram, on će gurnuti drugu povratnu adresu na pozivnu snop i tako dalje, s podacima koje se podudaraju i uništavaju kao što program diktira. Ako pritisak troši sav prostor namijenjen pozivnom snopu, dođe do pogreške nazvanog prelijevanja stanja , što općenito uzrokuje pad sustava . Dodavanje ulaza potprogramu u pozivni stog ponekad se zove "namatanje"; Obratno, uklanjanje unosa je "odmotavanje".

Obično je točno jedan poziv stog povezan s pokrenutim programom (ili točnije, sa svakim zadatkom ili nitom procesa ), iako se mogu stvoriti dodatni stogovi za rukovanje signalom ili kooperativno višezadaćanje (kao s setcontextom ). Budući da postoji samo jedan u ovom važnom kontekstu, može se nazvati i stog (implicitno, "zadatka"); Međutim, u Forthovom programskom jeziku bilježnica ili skup parametara se pristupa eksplicitnije od pozivnog stanja i obično se naziva stog (vidi dolje).

U programskim jezicima na visokoj razini , specifičnosti pozivnog stanja obično su skrivene od programera. Daju se pristup samo skupu funkcija, a ne memorije na samom slogu. Ovo je primjer apstrakcije . S druge strane, većina sastavnih jezika zahtijeva da programeri budu uključeni u manipuliranje stogom. Stvarni detalji stoga u programskom jeziku ovise o prevodiocu , operativnom sustavu i dostupnom skupu instrukcija .

Funkcije stupca poziva [ uredi ]

Kao što je gore navedeno, primarna svrha pozivnog stanja je pohranjivanje povratnih adresa . Kada se pozove podrutina, mjesto (adresa) instrukcije na kojoj se kasnije može nastaviti treba spasiti negdje. Upotreba stalka za spremanje povratne adrese ima važne prednosti u odnosu na alternativne pozivne konvencije . Jedna je od toga da svaki zadatak može imati vlastiti stog, a time i potprogram može biti povratan , tj. Može biti aktivan istodobno za različite zadatke koji rade različite stvari. Još jedna prednost je ta da se rekurzija automatski podržava. Kada se funkcija zove recurzivno, potrebno je pohraniti povratnu adresu za svaku aktivaciju funkcije kako bi se kasnije mogla koristiti za povratak od aktivacije funkcije. Stack strukture pružaju ovu sposobnost automatski.

Ovisno o jeziku, operacijskom sustavu i strojnom okruženju, pozivni stog može poslužiti i za druge svrhe, uključujući:

Lokalno pohranjivanje podataka


Subroutine često zahtijeva memorijski prostor za pohranu vrijednosti lokalnih varijabli , varijable koje su poznate samo u aktivnom potprogramu i ne zadržavaju vrijednosti nakon što se vrati. Često je prikladno dodijeliti prostor za tu upotrebu jednostavnim premještanjem vrha stogova dovoljno da se osigura prostor. Ovo je vrlo brzo u usporedbi s raspodjelom dinamičke memorije koja koristi prostor hrpe . Imajte na umu da svaka zasebna aktivacija subroutine dobiva vlastiti zasebni prostor u stog za lokalno stanovništvo.


Prolazak parametara


Subroutines često zahtijevaju da se vrijednosti za parametre isporučuju kodom koji ih zove, a nije neuobičajeno da prostor za te parametre može biti postavljen u pozivnom snopu. Općenito, ako postoji samo nekoliko manjih parametara, registri procesora će se koristiti za prosljeđivanje vrijednosti, ali ako postoji više parametara nego što se to može riješiti na taj način, potreban je memorijski prostor. Pozivni snop dobro funkcionira kao mjesto za te parametre, pogotovo jer svaki poziv u potprogram, koji će imati različite vrijednosti za parametre, bit će dodijeljen zaseban prostor na pozivnom snopu za te vrijednosti.


Procjena snopa


Operandi za aritmetičke ili logičke operacije najčešće se smještaju u registre i upravljaju tamo. Ipak, u nekim situacijama operandi se mogu slagati do proizvoljne dubine, što znači nešto više nego što se moraju koristiti registri (ovo je slučaj izlijevanja registra ). Snop takvih operandi, prilično sličan onom u RPN kalkulatoru , zove se evaluacijski sloj i može zauzeti prostor u pozivnom slogu.


Pointer na trenutnu instancu


Neki jezici usmjereni na objekte (npr. C + + ) pohranjuju ovaj pokazivač uz argumente funkcije u pozivnom slogu prilikom pozivanja na metode. Ovaj pokazivač upućuje na instancu objekta povezanu s metodom koju treba pozvati.


Uključivanje kontekstu potprograma


Neki programski jezici (npr. Pascal i Ada ) podržavaju deklaraciju ugniježđenih potprogrami kojima je dopušteno pristupiti kontekstu njihovih priloženih rutina, tj. Parametara i lokalnih varijabli unutar opsega vanjskih rutina. Takvo statično gniježđenje može ponoviti - funkcija koja se deklarira unutar funkcije koja se deklarira unutar funkcije ... Provedba mora pružiti sredstvo pomoću koje pozvana funkcija u bilo kojoj određenoj statičkoj razini gniježđenja može referencirati okvir za ogradu na svakoj razini približavanja gniježđenja. Uobičajeno je da se ta referenca provodi pomoću pokazivača u okvir nedavno aktiviranog primjerka funkcije zatvaranja, nazvanu "downstack link" ili "static link", kako bi ga se razlikovalo od "dinamičke veze" koja se odnosi na neposrednog pozivatelja ( Koja ne mora biti staticna roditeljska funkcija).


Umjesto statičke veze, reference na statičke okvire koji se mogu priložiti mogu se skupiti u niz točaka poznatih kao prikaz koji je indeksiran za lociranje željenog okvira. Dubina rutinskih leksičkih gniježđenja je poznata konstanta, tako da je veličina rutinskog prikaza fiksna. Također, poznat je i broj opsega koji obuhvaćaju trake, a indeks na zaslonu je također fiksiran. Obično se rutinski prikaz nalazi u vlastitom okviru, no Burroughs B6500 implementirao je takav zaslon u hardveru koji podržava do 32 razine statičkog gniježđenja.


Unosi zaslona koji označavaju sadržavaju opsega dobiveni su iz odgovarajućeg prefiksa zaslona pozivatelja. Unutarnja rutina koja rekordira stvara zasebne okvire poziva za svaku zazivnicu. U ovom slučaju, sve statičke veze unutarnje rutine upućuju na isti vanjski rutinski kontekst.


Ostalo stanje povratka


Pored adrese vraćanja, u nekim okruženjima može postojati i druga stanja stroja ili softvera koja se trebaju vratiti kada se vrati subroutine. To može uključivati stvari kao što su razina povlastice, informacije o upravljanju iznimkama, aritmetičke načine itd. Ako je potrebno, to se može pohraniti u pozivnu snop kao i povratna adresa.


Tipični pozivni snop koristi se za povratnu adresu, lokalne stanice i parametre (poznat kao okvir poziva ). U nekim okruženjima može postojati više ili manje funkcija dodijeljenih pozivnom snopu. Na Forthovom programskom jeziku , na pozivnim snopom (koji u tom okruženju naziva se povratni stog ), obično se samo povratna adresa, brojčani parametri petlje i indeksi, a možda i lokalne varijable pohranjuju, iako se svi podaci mogu privremeno postaviti Tamo korištenjem posebnog koda za rukovanje stalnim povratima sve dok se poštuju potrebe poziva i povrataka; Parametri se obično pohranjuju na zasebnom skupu podataka ili skupu parametara , obično se naziva stog u Forth terminologiji iako postoji pozivni stog jer se obično pristupa eksplicitnije. Neki Forthovi također imaju treći stog za parametre s pomičnim točkama .

Struktura [ uredi ]

Raspored stanja poziva

Skupni poziv sastoji se od stognih okvira (koji se nazivaju i aktivacijski zapisi ili okviri za aktivaciju ). To su ovisne o stroju i ABI- ovisne strukture podataka koje sadrže podatke o stanju podataka. Ti se podaci ponekad nazivaju i CFI (Call Frame Information). [1] Svaki okvir stog odgovara pozivu na potprogram koji još nije završio povratkom. Na primjer, ako je pokrenuta potprogramka pod nazivom DrawLine , koju je nazvao DrawSquare , gornji dio pozivnog stanja može biti postavljen kao na slici s desne strane.

Ovakav dijagram može se nacrtati u oba smjera sve dok se pojavi položaj vrha, a time i smjera rasta stupa. Nadalje, neovisno o tome, arhitekture se razlikuju u tome hoće li se broj poziva povećavati prema višim adresama ili prema nižim adresama. Logika dijagrama ne ovisi o izboru adresiranja.

Okvir stog na vrhu stog je za trenutno izvršavajuću rutinu. Okvir stog obično uključuje najmanje sljedeće stavke (u redoslijedu):

  • Argumenti (vrijednosti parametara) preneseni u rutinu (ako ih ima);

  • DrawLine adresu natrag na pozivatelja rutine (npr. U okviru DrawLine stupa, adresu u DrawSquare kod); i

  • Prostor za lokalne varijable rutine (ako ih ima).

Upori za stog i okvir [ uredi ]

Kada se veličine okvira stalka mogu razlikovati, kao što je između različitih funkcija ili između poziva određene funkcije, iskakanje okvira sa stog ne predstavlja fiksno smanjenje pokazivača stogova . Pri povratnoj funkciji, pokazivač stupa umjesto toga vraća se na pokazivač okvira , vrijednost pokazivača stupa neposredno prije pozivanja funkcije. Svaki okvir stupa sadrži pokazivač stog na vrh okvira koji se nalazi odmah ispod. Stack pointer je promjenjivi registar koji se dijeli između svih poziva. Okvirni pokazivač zadanog zazivanja funkcije je kopija pokazivača stogova kao što je bio prije pozivanja funkcije. [2]

Položaji svih ostalih polja u okviru mogu se definirati relativno ili na vrhu okvira, kao negativne offsets pokazivača stogova ili u odnosu na gornji dio okvira kao pozitivni pomak okvira okvira. Položaj samog okvirnog pokazivača mora biti inherentno definiran kao negativni pomak pokazivača stupa.

Pohranjivanje adrese u okvir pozivatelja [ uredi ]

U većini sustava okvir stog ima polje koje sadrži prethodnu vrijednost registra pokazatelja okvira, vrijednost koju je imao dok je izvršio pozivatelj. Na primjer, okvir snopa DrawLine bi mjesto na kojem se nalazi memorijska vrijednost pokazivača okvira koju koristi DrawSquare (nije prikazan na gornjem dijagramu). Vrijednost se sprema nakon unosa u potprogram i vraća se po povratku. Imanje takvog polja na poznatoj lokaciji u okviru stog omogućuje kodu da svaki okvir dobije sukcesivno ispod okvira trenutačno izvršenih rutina, a također omogućuje rutinu da lako vratiti pokazivač okvira u okvir pozivatelja , neposredno prije nego što se vrati.

Leksički ugniježđene rutine [ uredi ]

Daljnje informacije: Ugniježđena funkcija i ne-lokalna varijabla

Programski jezici koji podržavaju ugniježđene potprograme također imaju polje u okviru poziva koji ukazuje na okvir stupa najnovije aktivacije postupka koji najbliže obuhvaća kallee, tj. Neposredni opseg kalleea. To se naziva pristupna veza ili statična veza (jer bilježi statičko gniježđenje tijekom dinamičkih i rekurzivnih poziva) i pruža rutinu (kao i sve druge rutine koje može pozvati) pristup lokalnim podacima svojih encapsuliranih rutina pri svakom gniježđenju razina. Neke arhitekture, kompilatori ili slučajevi optimizacije pohranjuju jednu vezu za svaku ogradu (ne samo neposredno zatvaranje), tako da duboko ugniježđene rutine koje pristupaju plitkim podacima ne moraju prolaziti kroz nekoliko veza; Ova strategija se često naziva "prikaz". [3]

Pristupne veze mogu biti optimizirane kada unutarnja funkcija ne može pristupiti (ne-konstantnim) lokalnim podacima u enkapsulaciji, kao što je slučaj kod čistih funkcija koje komuniciraju samo putem argumenata i povratnih vrijednosti. Neka povijesna računala, poput velikih sustava Burroughsa , imala su posebne "reklame za prikaz" kako bi podržavale ugniježđene funkcije, a sastavljači za najsuvremenije strojeve (kao što je sveprisutni x86) jednostavno rezerviraju nekoliko riječi na snopu po pokazivačima, po potrebi.

Preklapanje [ uredi ]

U nekim se svrhama okvir stanja potprogramu i njegovog pozivatelja može smatrati preklapanjem, preklapanje se sastoji od područja gdje se parametri prenose od pozivatelja do kalleea. U nekim okruženjima pozivatelj gura svaki argument na stog, čime se produžuje okvir stupa, a zatim poziva kallee. U drugim okruženjima, pozivatelj ima unaprijed dodijeljeno područje na vrhu svojeg stupa kako bi zadržalo argumente koje opskrbljuje drugim potprogramima koje poziva. Ovo područje se ponekad naziva područje odlaska za argumente ili područje za obradu poziva . Prema ovom pristupu, prevodilac izračunava veličinu područja kako bi bio najveći koji je potreban bilo kojem nazvanom potprogramu.

Upotrijebite [ uredi ]

Obrada mjesta poziva [ uredi ]

Obično je manipulacija pozivnim stogom potrebna na mjestu poziva na potprogram je minimalna (što je dobro jer može postojati mnogo pozivnih mjesta za svaku potprogramu koja se naziva). Vrijednosti za stvarne argumente vrednuju se na pozivnom mjestu, budući da su specifične za određeni poziv, i guraju se na stog ili se stave u registre, kako je određeno korištenjem konvencije poziva . Stvarna uputa za pozivanje, kao što je "grana i veza", obično se izvodi za prijenos kontrole na kôd ciljne potprogram.

Obrada ulaznih subroutine [ uredi ]

U pozvanoj potprogramu prvi izvršeni kod obično se naziva prologom potprograma , budući da započinje nužnim održavanjem prije koda za izjave rutine.

Prolog će obično spremiti povratnu adresu koja je ostala u registru pomoću uputa za poziv gurajući vrijednost na pozivnu snop. Slično tome, trenutni pokazivač stabla i / ili vrijednosti okvira pokazivača mogu se gurnuti. Alternativno, neke arhitekture postavljene za naredbe automatski pružaju usporedivu funkcionalnost kao dio akcije samog uputa za poziv, a u takvom okružju prolog ne mora to učiniti.

Ako se koriste okvirni pokazivači, prolog obično će postaviti novu vrijednost registra okvira pointera iz pokazivača stupa. Prostor na hrpu za lokalne varijable može se dodijeliti inkrementalno mijenjanjem stog pokazivača.

Forth programski jezik omogućuje eksplicitno navijanje pozivnog stanja (tamo se naziva "povratni stog").

Obrada povrata [ uredi ]

Kada je potprogram spreman za povratak, izvršava epilog koji poništava korake prologa. To će tipično vratiti pohranjene vrijednosti registara (kao što je vrijednost pokazivača okvira) iz okvira stogova, pop čitav stog stabla iz stoga promjenom vrijednosti pokazivača stanja i konačno podružnice na uputu na povratnoj adresi. Pod mnogim pozivnim konvencijama stavke su izbacile iz stupa s epilogom koji uključuje izvorne vrijednosti argumenta, u kojem slučaju obično ne postoje daljnje manipulacije stogova koje treba obaviti pozivatelj. Međutim, s nekim konvencijama o pozivima, odgovornost je pozivatelja da uklonite argumente iz stupa nakon povratka.

Otključavanje [ uredi ]

Vraćanje iz pozvane funkcije će ukloniti gornji okvir iz stupa, možda ostavljajući povratnu vrijednost. Općenitije činanje iskakanja jednog ili više okvira sa stogova za nastavak izvršavanja drugdje u programu zove se raspustanje stupa i mora se izvršiti kada se koriste ne-lokalne upravljačke strukture, kao što su one koje se koriste za upravljanje iznimkom . U tom slučaju, okvir stanja funkcije sadrži jedan ili više unosa koji navode rukovatelje izuzetaka. Kada se izbaci iznimka, stog se odmotava sve dok se ne pronađe rukovatelj koji je spreman postupati (uhvatiti) vrstu izbačene iznimke.

Neki jezici imaju druge kontrolne strukture koje zahtijevaju opće odvijanje. Pascal dopušta globalnu goto izjavu za prijenos kontrole iz ugniježđene funkcije u prethodno pozivanu vanjsku funkciju. Ova operacija zahtijeva odstupanje stogova, uklanjajući onoliko snopnih okvira koliko je potrebno kako bi se vratio odgovarajući kontekst za prijenos kontrole na ciljni izvatak unutar vanjske funkcije. Slično, C ima setjmp i longjmp funkcije koje djeluju kao ne-lokalni gotos. Zajednički Lisp omogućuje kontrolu onoga što se događa kada se stalak odveze pomoću posebnog operatora za unwind-protect .

Prilikom primjene nastavka , stog se (logički) odmotava, a potom se vraća sa snopom nastavka. Ovo nije jedini način provedbe nastavaka; Na primjer, korištenjem višestrukih, eksplicitnih stackova, primjena nastavka može jednostavno aktivirati njegov stog i vjetar vrijednost koju treba proslijediti. Programski jezik Scheme omogućuje izvršavanje proizvoljnih thunks u određenim točkama na "unwinding" ili "rewinding" kontrolnog stoga kada se nastavlja poziv.

Inspekcija [ uredi ]

Vidi također: Profiliranje (računalno programiranje)

Niz poziva ponekad se može pregledati dok se program izvodi. Ovisno o načinu pisanja i sastavljanja programa, informacije o snopu mogu se koristiti za određivanje srednjih vrijednosti i funkcija pozivnih tragova. Ovo je korišteno za generiranje finih zrnatih automatskih testova [4] i u slučajevima poput Ruby i Smalltalk, za primjenu prvoklasnih nastavaka. Kao primjer, GNU Debugger (GDB) provodi interaktivni pregled stanja poziva pokrenutog, ali pauziranog, C programa. [5]

Uzimanje uobičajenih uzoraka pozivnog stanja može biti korisno u profiliranju izvedbe programa, jer ako se brojčani podaci o uzorkovanju pojavljuju na podacima o pozivnom stogu, vjerojatno je usko grlo na kodu i trebalo bi se pregledati za probleme s performansama.

Sigurnost [ uredi ]

Glavni članak: Prenaponski buffer overflow

Na jeziku koji sadrži slobodne pokazivače ili ne-provjerene polje piše (npr. U C), miješanje podataka kontrolnog toka koji utječe na izvršenje koda (povratne adrese ili spremljene okvirne pokazatelje) i jednostavne programske podatke (parametre ili povratne vrijednosti ) U pozivnom snopu sigurnosni je rizik, a moguće je iskoristiti preko preljeva međumemorije stupa kao najčešći tip preljeva međuspremnika .

Jedan od takvih napada uključuje popunjavanje jednog međuspremnika s proizvoljnim izvršnim kodom, a potom prelijevanjem istog ili nekog drugog međuspremnika da biste prebrisali neku povratnu adresu s vrijednošću koja upućuje izravno na izvršni kôd. Kao rezultat toga, kada se ta funkcija vraća, računalo izvršava taj kôd. Ovakav napad može se lako blokirati s W ^ X. [ Citat potreban ] Slični napadi mogu uspjeti čak i uz zaštitu W ^ X, uključujući povratak na libc napad ili napade koji dolaze iz programa usmjerenog na povratak . Predložene su različite ublažavanja, kao što su pohranjivanje polja na potpuno odvojenu lokaciju s povratnog stanja, kao što je to slučaj na Forth programskom jeziku. [6]