Википедија

Pozivni stek

Pozivni stek, u informatici, je struktura stek podataka koja čuva informacije o aktivnim potprogramima računarskog programa. Ova vrsta steka je takođe poznata kao izvršni stek, stek kontrole, rantajm stek ili mašina steka, i često skraćeno kao "gomila". Iako je održavanje poziva steka važno za pravilno funkcionisanje većine softvera, detalji su obično skriveni i automatski u programskim jezicima visokog nivoa. Mnoge računarske instrukcije seta obezbeđuju posebna uputstva za manipulaciju steka.

Pozivni stek se koristi za nekoliko povezanih svrha, ali glavni razlog je da pratite tačke u kojoj svaki aktivni potprogram treba da vrati kontrolu kada se završi izvršavanje. Aktivni potprogram je onaj koji je pozvan, ali tek treba da završi izvršenje nakon čega kontrola treba da se preda do tačke poziva. Takva aktivacija potprograma može biti ugnježdena na bilo kom nivou (rekurzivnom kao poseban slučaj), pa stek strukture. Ako, na primer, potprogram DrawSquare poziva potprogram DrawLine iz četiri različita mesta, DrawLine mora da zna gde da se vrate kada se izvršenje završi. Da bi se to postiglo, adresa sledeće instrukcije poziva, povratna adresa, je prebačena na poziv steka sa svakog poziva.

Opis uredi

Pošto je pozivni stek organizovan kao gomila, pozivalac gura povratne adrese na stek, i pod nazivom potprograma, kada se završi, povuče povratne adrese izvan poziva steka i transfera kontrole na toj adresi. Ako se zove rutina poziva na još jedan potprogram, ona će gurnuti još jednu povratnu adresu na poziv steka, i tako dalje, sa informacijom gomilanja i razlaganja kako program diktira. Ako guraju, troši se sav prostor izdvojen za poziv steka, greška steka zvana prekoračenje steka, uglavnom uzrokuje da se program sruši. Dodavanje ulazaka potprograma za poziv steka se ponekad naziva "navijanje"; Nasuprot tome, uklanjanje unosa se "odmotava".

Obično postoji tačno jedan poziv steka povezan sa zadatim programom (ili tačnije, sa svakim zadatkom ili temom procesa), iako može biti kreiran dodatni stek za rukovanje signalima ili kooperativnim multitaskingom (kao i setkontekst). Pošto postoji samo jedan u ovom važnom kontekstu, može se nazvati stek (implicitno, "zadatka") međutim, u Fort programskom jeziku stek podataka ili parametar stek pristupa je više eksplicitan od poziva steka i obično se naziva stek (vidi dole).

U programskim jezicima visokog nivoa, specifičnosti u pozivu steka su obično skriveni od programera. Oni daju pristup samo sa setom funkcija, a ne memorije na samom steku. Ovo je primer apstrakcije. Većina jezika za montažu, s druge strane, zahtevaju od programera da budu uključeni u manipulaciju štosa. Stvarni detalji steka u programskom jeziku zavise od prevodioca, operativnog sistema, i raspoloživog seta instrukcija.

Funkcije pozivnog steka uredi

Kao što je već rečeno, osnovna svrha pozivnog steka je da skladišti povratne adrese. Kada se potprogram zove, lokacija (adresa) za nastavu na kojima se kasnije mogu nastaviti potrebna je da se negde sačuvana. Korišćenje steka da sačuvate povratne adrese ima značajne prednosti u odnosu na alternativne konvencije pozivanja. Jedna je da svaki zadatak ima svoj stek, a samim tim i potprogram može biti uvučen, odnosno, mogu biti aktivni istovremeno za različite zadatke da obavljaju različite stvari. Još jedna prednost je da je rekurzija automatski podržana. Kada funkcija sebe samu poziva rekurzivno, povratna adresa treba skladištiti svako aktiviranje funkcije tako da se kasnije može koristiti za vraćanje iz aktivacije funkcije. Ova mogućnost je automatski sa steka.

Pozivni stek može poslužiti u dodatne svrhe, u zavisnosti od jezika, operativnog sistema i mašina životne sredine. Među njima mogu biti:

  • Lokalno skladištenje podataka
Potprogramu često treba memorijski prostor za čuvanje vrednosti lokalnih promenljivih, promenljive koje su poznate samo u aktivnom potprogramu i ne zadržavaju vrednosti kada se vraćaju. Često je običaj da se izdvoji prostor za njihovo korišćenje jednostavnim pomeranjem vrha gomile od strane dovoljno da se obezbedi prostor. Ovo je vrlo brzo u odnosu na dinamičku raspodelu memorije, koji koristi gomilu prostora. Imajte na umu da svako odvojeno aktiviranje potprograma dobija svoj poseban prostor u steku za lokale.
  • Parametar donošenja
Potprogrami često zahtevaju da se vrednosti za parametre dostave od strane koda koji ih poziva, a nije redak slučaj da prostor za ove parametre može biti postavljena u pozivnom steku. Generalno, ako postoji samo nekoliko malih parametara, procesor registra će se koristiti da prođu vrednosti, ali ako postoji više parametara nego što se može rukovati na ovaj način, memorijski prostor će biti potreban. Pozivni stek radi dobro kao mesto za ove parametre, naročito jer svaki poziv za potprograme, koji će imati različite vrednosti za parametre, dobiće poseban prostor na pozivnom steku za te vrednosti.
  • Evaluacija steka
Operandi za aritmetičke ili logičke operacije se najčešće stavljaju u registre i rade tamo. Međutim, u nekim situacijama operandi mogu biti složeni do proizvoljne dubine, što znači nešto više nego što registri moraju da koriste (to je slučaj registra raspodele). Stek takvih operanada, a kao da je u OPN kalkulatoru, se naziva stek evaluacije, a mogu da zauzimaju prostor i u pozivnom steku.
  • Pokazivač trenutne instance
Neki objektno orijentisani jezici (npr S++), čuvaju ovaj pokazivač sa funkcijom argumenata u pozivnom steku kada pozivaju metode. Ovaj pokazivač ukazuje na objekat instance u vezi sa metodom gde će se pozivati.
  • Zaključivanje konteksta potprograma 
Neki programski jezici (npr, Paskal i Ada) podržavaju umetnute potprograme, omogućavajući unutrašnjoj rutini pristup kontekstu njegove spoljne okružene rutine, odnosno parametara i lokalnih promenljivih u okviru spoljašnje rutine. Takva statična ugnežđenja mogu da ponavljaju - funkciju proglašenu u funkciji proglašenoj u funkciji ... Implementacija mora da obezbedi sredstva kojima se zove funkcija u svakom statičkom nivou ugnežđenom pomoću referenci prihvatnog okvira na svakom nivou prihvatnog gnezda. Obično ta referenca sprovodi pokazivač na sveobuhvatnom okviru, koji se zove "donji stek link" ili "statična veza", da bi se razlikovalo od "dinamičkog linka" koja se odnosi na neposrednog pozivaoca (što ne mora biti funkcija roditelja) . Na primer, jezici često dozvoljavaju unutrašnjoj rutini da se rekurzivno pozove, što je rezultiralo višestrukim okvirima poziva za prizivanje unutrašnje rutine, svi čije statičke veze ukazuju na iste spoljašnje rutinske kontekste. Umesto statičkog linka, reference na prihvatnim statičkim okvirima mogu da budu naplaćene u niz pokazivača poznatih kao ekran koji je indeksiran da locira željeni okvir. Burroughs ogromni sistemi su imali takav ekran u hardveru koji je podržavao do 32 nivoa statičkog gniezda.
  • Drugo povratno stanje
Pored povratne adrese, u nekim sredinama mogu postojati druge mašine ili softveri koji navode da treba da se vrati kada je potprogram povratan. Ovo može uključivati stvari kao što su nivoi privilegija, izuzetak rukovanja informacijama, aritmetičkog režima, i tako dalje. Ako je potrebno, to može da se čuva na pozivnom steku kao povratna adresa.

Tipičan pozivni stek se koristi za povratnu adresu, lokala i parametara (poznat je kao pozivni okvir). U nekim sredinama može biti više ili manje funkcija koje su pozivni stek. U Fort programskom jeziku, na primer, obično samo povratna adresa, računajući parametre i indekse petlje, a eventualno lokalne promenljive su sačuvane na pozivni stek (koja je u tom okruženju i koja se zove povratni stek), mada neki podaci mogu biti privremeno postavljeni ne pomoću posebnog povratnog steka rukovanja koda toliko dugo kao potreba poziva i povratka koje se poštuju; parametri se obično čuvaju na odvojenom steku podataka ili parametara steka i obično se naziva štos u Fort terminologiji iako se pozivu steka obično pristupa više eksplicitno. Neki Fortovi imaju i treću hrpu za pomerajuće tačke parametara.

Struktura uredi

 
Izgled pozivnog steka

Pozivni stek se sastoji od okvira steka (takođe poznatog kao aktivacija evidencije ili aktivacija okvira). To su zavisne mašine i ABI-zavisne strukture podataka koje sadrže informacije o stanju potprograma. Ovi podaci se ponekad nazivaju i  CFI (pozivni ram informacija). [1] Svaki okvir steka odgovara pozivu potprogramima koji još nisu prestali sa povratkom. Na primer, ako potprogram po imenu DrawLine trenutno radi, pošto je pozvao potprogram DrawSquare, gornji deo pozivnog steka može biti postavljen kao na slici na desnoj strani.

Dijagram se ovako može izvući u oba smera dok je plasman u vrhu, po smeru rasta steka, podrazumeva se. Osim toga, nezavisno od toga, arhitekture razlikuju oko toga da li poziv steka raste ka višoj adresi ili ka nižoj adresi. Logika dijagrama je nezavisna od adresiranja izbora.

Stek okvira na vrhu gomile je za trenutno izvršavanje rutine. Stek okvira obično uključuje najmanje sledeće stavke (u redosledu):

  • argumenti (vrednosti parametara) doneti na rutinu (ako ih ima)
  • povratna adresa će se vratiti sagovorniku rutine (npr u DrawLine stek okviru, adrese u DrawSquare koda) i
  • prostor za lokalne promenljive u rutinu (ako ih ima).

Stek i  pokazivači okvira uredi

Kada veličine stek okvira mogu da se razlikuju, kao što je između različitih funkcija ili između prizivanja određene funkcije, iskakanje okvira sa steka i to ne predstavlja fiksno smanjenje pokazivača steka. U funkciji povratka, stek pokazivač umesto da vrati okvir pokazivača, vrednost stek pokazivača neposredno pre funkcija je nazvana. Svaki stek okvir sadrži stek pokazivač na vrhu okvira odmah ispod. Stek pokazivač je promenljivi registar koji se deli između svih priziva. Okvir kazaljka datog pozivanja na funkcije je kopija steka pokazivača jer je pre nego što je funkcija pozvana.[2]

Lokacije svih drugih oblasti u okviru mogu biti definisane u odnosu na vrh okvira, kao kompenzacija negativnog steka pokazivača, ili u odnosu na vrh okvira ispod, kao pozitivne kompenzacije okvira pokazivača. Položaj okvira sam po sebi mora biti definisan kao negativna kompenzacija steka pokazivača.

Čuvanje adresu na okviru pozivaoca uredi

U većini sistema stek okvir mora da sadrži polje prethodne vrednosti okvira pokazivača registra, vrednost koju je imao dok se sagovornik izvršavao. Na primer, stek okvira DrawLine će imati memorijsku lokaciju koja drži pokazivač vrednosti okvira koji DrawSquare koristi (koje nisu prikazane u dijagramu gore). Vrednost je spašena nakon ulaska u potprogram i obnovljena nakon povratka. Imajući takvu oblast u poznatoj lokaciji u okviru steka omogućava kod za pristup svakom okviru sukcesivno ispod okvira u trenutnoj izvršavanoj rutini, a takođe omogućava rutini da lako vrati okvirni pokazivač na okvir pozivaoca, neposredno pred vraćanja.

Leksički ugnežđene rutine uredi

Dodatna literatura: Ugnežđena funckija i Ne-lokalna promenljiva

Programski jezici koji podržavaju ugnežđene potprograme takođe imaju polje u okviru poziva koji upućuju na stek okvir najnovije aktiviranje procedure koja najpribližnije inkapsulira pozvani, odnosno neposredni okvir pozvanog. To se zove veza pristupa ili statična veza (kao što prati statičko gnezdo u dinamiknim i rekurzivnim pozivima) i daje rutinu (kao i bilo koje druge rutine koje mogu da se pozovu) pristup lokalnim podacima svojih inkapsuliranim rutinama u svakom ugnežđenom nivou. Neke arhitekture, prevodioci, ili slučajevi optimizacija nekog linka za svaki nivo, tako da je duboko ugnežđene rutine koje pristupaju plitkim podacima ne moraju da prolaze nekoliko linkova; ova strategija se često naziva "ekran".[3]

Pristupni linkovi mogu biti optimizovani daleko kada se unutrašnjoj funkciji ne može pristupati (nije konstanta) lokalnim podacima, kao što je to slučaj sa čistim funkcijama koje komuniciraju samo putem argumenata i povratnih vrednosti, na primer. Neki istorijski računari, kao što su Burroughs velikih sistema, imali posebne "registre ekrana" da podrži ugnežđene funkcije, dok kompajleri NA najsavremenijim mašinama (kao što su sveprisutne x86) jednostavno zadržavaju nekoliko reči na steku za pokazivače, po potrebi.

Preklapanje uredi

Za neke svrhe, stek okvira od potprograma i od svog sagovornika može se smatrati da se preklapaju, preklapanje se sastoji od područja gde se donose parametri od sagovornika. U nekim sredinama, sagovornik gura svaki argument na stek, čime produžava svoj stek okvir, a zatim priziva pozvani. U drugim sredinama, pozivalac ima prostor na vrhu svog stek okvira da drži argumente koje snabdeva sa drugim potprogramima. Ovo područje se ponekad naziva oblast odlaznog argumenata ili. Prema ovom pristupu, veličina prostora se obračunava po kompajleru da je to najveća potrebna bilo koja  pozvana od strane potporgrama. 

Primena uredi

Poziv za obradu položaja uredi

Obično je poziv stek manipulacije potrebno na mestu poziva potprograma (što je dobro, jer ne može biti mnogo položaja poziva za svaki potprogram da se zove). Vrednosti stvarnih argumenata se procenjuju na poziv položaja, jer su specifične za određeni poziv, kao što je određeno konvencijom. Stvarna instrukcija poziva, kao što su "grane i link", onda se obično izvršavaju tako da prenesu kontrolu koda ciljanog potprograma.

Potprogram za obradu unosa uredi

U pozovanom potprogramu, prvi kod izvršavanja se obično naziva potprogram prologa, jer radi neophodno pospremanje koda za izjave rutine koja je počela.

Prolog će obično sačuvati povratnu adresu levo u registru od strane instrukcija poziva guranjem vrednosti na pozivni stek. Slično tome, sadašnji stek pokazivač i / ili okvir pokazivača vrednosti mogu biti gurnuti. Alternativno, neki set instrukcija arhitekture automatski daje porediti funkcionalnost kao deo akcije instrukcije koja poziva samu sebe, a u takvom okruženju prolog se ne mora uraditi.

Ako se koriste okviri pokazivača, prolog će obično postaviti novu vrednost okvira pokazivača registra sa steka pokazivača. Prostor na stek za lokalne promenljive se onda može izdvojiti postepeno kako se menja stek pokazivača.

Fort programski jezik dozvoljava eksplicitno namotavanje pozivnog steka (tzv.  "povratni stek").

Povratna obrada uredi

Kada je potprogram spreman da se vrati, ona izvršava epilog koji opoziva korake prologa. Ovo će obično povratiti sačuvane vrednosti registra (kao okvir pokazivača vrednosti) iz steka okvira, i na kraju grana na uputstvu na povratnu adresu. U mnogim pozivanjima konvencija stavke je pukla što je epilog uključivanja originalnog argumenta vrednosti. Sa nekim pozivanjem konvencija, međutim, daje se odgovornost sagovornika da ukloni argumente iz steka nakon povratka.

Odmotavanje uredi

Vraćajući se od strane pozvane funkcije koja će se pojaviti na vrhu okvira sa steka, možda ostavljajući povratnu vrednost. Što više opštih akta iskakanja jednog ili više okvira sa gomile da nastave izvršenje na drugom mestu u programu koji se zove stek odmotavanja i mora se izvršiti kada se koriste nelokalne kontrolne strukture, kao što su oni koji se koriste za korišćenje izuzecima. U tom slučaju, stek okvir funkcija sadrži jedan ili više ulazaka koje određuju izuzetak. Kada je bačen izuzetak, stek se odmotava da se utvrdi da li je spreman za korišćenje.

Neki jezici imaju i druge kontrolne strukture koje zahtevaju odmotavanje. Paskal omogućava globalni GoTo izjavu da prenese kontrolu iz funkcije i u prethodno pozvanoj spoljnoj funkciji. Ova operacija zahteva da se odmotava stek, uklanja onoliko stek okvira neophodnih da se obnovi odgovarajući kontekst kako bi se prenela kontrola na ciljnu izjavu u prihvatnoj spoljašnjoj funkciji. Slično tome, S ima setjmp i longjmp funkcije koje deluju kao nelokalni GoTo. Common Lisp omogućava kontrolu nad onim što se dešava kada se odmotava stek pomoćuunwind-protect posebnog operatera.

Prilikom podnošenja zahteva za nastavak, stek se (logično) odmotava, a potom zamotava sa gomile nastavka. Ovo nije jedini način za sprovođenje nastavka; na primer, koristeći više, eksplicitne gomile, primena nastavka može jednostavno aktivirati svoj stek i vrednost da bude usvojena. Scheme programski jezik dozvoljava proizvoljno da se izvrši u određenim tačkama na "odmotavanju" ili "premotavanju" u kontrolnom steku kada se pokrene procedura za nastavak.

Pregled uredi

Vidi još: Profilisanje (računarstvo) i Duboko uzorkovanje

Pozivni stek može ponekad biti pregledan kao program izvršavanja. U zavisnosti od toga kako je program napisan i sastavljen, informacije o steku mogu da se koriste za određivanje međurezultata i tragova funkcije poziva. Ovo se koristi za generisanje fine strukture automatskih testova,[4] i u slučajevima kao što su Rubi i Smalltalk, da sprovedu prvoklasne nastavke. Kao primer, GNU dibager (GDB) sprovodi interaktivni uvid u pozivni stek jednog poziva, ali je zastao, S program.[5]

Uzimajući redovno radno vreme uzorka iz pozivnog steka može biti korisno u profilisanju performansi programa, jer ako se pokazivač potprograma pojavljuje na pozivnom steku uzorkovanja podataka mnogo puta, verovatno je šifra uskog grla i treba proveravati za probleme performansi.

Bezbednost uredi

Glavni članak: Stek bafera prelivanja

U jeziku sa slobodnim pokazivačima ili neproverenim nizom piše (kao u S), mešanje podataka kontrole protoka utiče na izvršenje koda (vraća adrese ili sačuvane okvire pokazivača) i jednostavne podatke programa (parametre ili povratne vrednosti) u pozivnom steku i to je bezbednosni rizik, moguće je eksploatisati preko steka bafera prelivanja kao najčešći tip bafera prelivanja.

Jedan od takvih napada podrazumeva punjenje jednog bafera sa proizvoljnim izvršnim kodom, a zatim prelivanje istog ili neki drugog bafera da prepiše neku povratnu adresu sa vrednošću koja ukazuje direktno na izvršni kod. Kao rezultat toga, kada se funkcija vraća, računar izvršava taj kod. Ova vrsta napada se može lako blokirati W^X. Slični napadi mogu uspeti čak i sa W^X omogućenom zaštitom, uključujući i povratni napad kompajler ili napada povratno orijentisanog programiranja. Razna ublažavanja su predložena, kao što je skladištenje nizova u potpuno odvojenoj lokaciji od povratnog steka, kao što je to slučaj u Fort programskom jeziku.[6]

Vidi još uredi

Reference uredi

  1. ^ Nicholas Carlini and David Wagner.
  2. ^ "Understanding the Stack". cs.umd.edu. 2003-06-22.
  3. ^ Alternative Microprocessor Design
  4. ^ McMaster, S.; Memon, A. (2006).
  5. ^ "Debugging with GDB: Examining the Stack" Arhivirano na sajtu Wayback Machine (14. april 2021). chemie.fu-berlin.de. 1997-10-17.
  6. ^ Doug Hoyte.

Literatura uredi

Spoljašnje veze uredi

Preuzeto iz „https://sr.wikipedia.org/w/index.php?title=Позивни_стек&oldid=26976838”