Dom > Izložba > Sadržaj

Prikazni registar ili struktura podataka, za lociranje okvira stega ugneženih funkcija u računarskom programiranju

Apr 22, 2017

Pozovite broj

U računarskoj nauci , stack poziv je struktura podataka o stacku koja čuva informacije o aktivnim potprogramima računarskog programa . Ova vrsta stacka je poznata i kao stack izvršenja , programski stack , kontrolni stack , stack run-time ili stack mašina i često se skraćuje samo na "stack". Iako je održavanje skupa poziva važno za pravilno funkcionisanje većine softvera , detalji su obično skriveni i automatski u programskim jezicima visokog nivoa . Mnogi setovi kompjuterskih instrukcija pružaju posebna uputstva za manipulaciju štapovima.

Stek poziva se koristi u nekoliko srodnih razloga, ali glavni razlog za to je da pratite tačku na koju svaka aktivna potprograma treba vratiti kontrolu kada završi izvršavanje. Aktivna podprograma je ona koja je pozvana, ali tek treba izvršiti izvršenje, nakon čega kontrolu treba vratiti tačku poziva. Takve aktivacije podprograma mogu biti ugnežene na bilo koji nivo (rekurzivno kao poseban slučaj), stoga struktura stuba. Ako, na primer, podprogram DrawSquare naziva podprogram DrawLine sa četiri različita mesta, DrawLine mora znati gdje se vratiti kada se njegovo izvršenje završi. Da bi se ovo postiglo, adresa koja sledi instrukciju poziva, povratna adresa , se guruje u stack poziv sa svakim pozivom.


Sadržaj

[ Sakrij ]


Opis [ uredi ]

Budući da je stack poziva organizovan kao stack , pozivalac gura povratnu adresu na stack, a pozivana potprograma, kada završi, povlači ili popušta povratnu adresu iz stega poziva i prenese kontrolu na tu adresu. Ako pozvana potprograma poziva još jednu potprogramu, ona će potisnuti drugu adresu za povratak u stack poziva i tako dalje, uz informaciju koja se skladišti i odustaje dok program diktira. Ako guranje potroši sve prostorije dodijeljene za stack poziva, javlja se greška koja se naziva preliv u stacku , uopšte uzrokujući da program pada . Dodavanje stavke podprograma u stack poziva se ponekad naziva "namotavanje"; Obratno, uklanjanje unosa je "opuštanje".

Obično postoji jedan broj stika koji se povezuje sa pokretnim programom (ili tačnije, sa svakim zadatkom ili threadom procesa ), iako se mogu kreirati dodatni stackovi za rukovanje signalima ili zadatke za više zadataka (kao i za setcontext ). Budući da postoji samo jedan u ovom važnom kontekstu, može se nazvati i stack (implicitno, "zadatka"); Međutim, na programskom jeziku Forth, stack podataka ili stack parametara se pristupa eksplicitnije od stack poziva i obično se naziva stack (pogledaj ispod).

U programskim jezicima visokog nivoa , specifičnosti stack poziva su obično skrivene od programera. Daju im pristup samo skup funkcija, a ne memorije na samom stegu. Ovo je primer apstrakcije . Većina jezika za sklapanje , s druge strane, zahtijeva od programera da se uključe u manipulaciju sa stackom. Stvarni detalji stega u programskom jeziku zavise od kompajlera , operativnog sistema i dostupnog skupa instrukcija .

Funkcije stack poziva [ uredi ]

Kao što je već pomenuto, primarna svrha kupa poziva je da čuva povratne adrese . Kada se poziva potprogram, lokacija (adresa) instrukcije na kojoj se kasnije može nastaviti treba negdje da se sačuva. Korišćenje štapa za čuvanje povratne adrese ima važne prednosti u odnosu na konvencije alternativnih poziva . Jedna je da svaki zadatak može imati svoj stack, pa se potprogram može ponovo uključiti, odnosno može biti istovremeno aktivan za različite zadatke koji rade različite stvari. Još jedna prednost je što se rekurzija automatski podržava. Kada se funkcija poziva rekurzivno, treba vratiti adresu za svako aktiviranje funkcije tako da se kasnije može koristiti da se vrati iz aktivacije funkcije. Stek strukture omogućavaju ovu mogućnost automatski.

U zavisnosti od jezika, operativnog sistema i okruženja mašine, stog poziva može da služi dodatnim namerama, uključujući na primer:

Lokalno skladištenje podataka


Podprogramu često je potreban memorijski prostor za čuvanje vrednosti lokalnih varijabli , varijabli koje su poznate samo unutar aktivne potprograma i ne zadržavaju vrijednosti nakon povratka. Često je pogodno dodijeliti prostor za ovu upotrebu jednostavnim pomjeranjem vrha staka dovoljno da obezbedi prostor. Ovo je vrlo brzo u poređenju sa dinamičkom alokacijom memorije , koja koristi prostor kupovine . Imajte na umu da svako zasebno aktiviranje potprograma dobija svoj zaseban prostor u stacku za mještane.


Prolaz parametara


Podprogrami često zahtevaju da im vrijednosti za parametre budu snabdevene kodom koji ih poziva, i nije neuobičajeno da prostor za ove parametre može biti postavljen u stack pozivima. Uopšteno, ako ima samo nekoliko malih parametara, registratori procesora će se koristiti za prosljeđivanje vrijednosti, ali ako ima više parametara nego što se to može riješiti na ovaj način, potreban je memorijski prostor. Pozivi za pozive dobro funkcionišu kao mesto za ove parametre, posebno pošto će svaki poziv podprogramu koji će imati različite vrednosti za parametre biti dodeljen zasebnom prostoru u stacku poziva za te vrednosti.


Stack Evaluation


Operanti za aritmetičke ili logičke operacije se najčešće stavljaju u registre i rade tamo. Međutim, u nekim situacijama se operandi mogu složiti do proizvoljne dubine, što znači nešto više od registara koji se moraju koristiti (to je slučaj s popisom registra ). Sastav takvih operandi, poput onog u RPN kalkulatoru , naziva se procenjivački stack i može zauzeti prostor u stacku poziva.


Pokazivač na trenutnu instancu


Neki objektno orijentisani jezici (npr. C ++ ) čuvaju ovaj pokazivač zajedno sa argumentima funkcija u stomaku poziva kada se pozivaju na metode. Ovaj pokazivač ukazuje na instancu objekta pridruženu metodu za koju se poziva.


Uključivanje konteksta potprograma


Neki programski jezici (npr. Pascal i Ada ) podržavaju deklaraciju ugneženih potprograma , kojima je omogućeno pristup kontekstu njihovih okruženja, tj. Parametara i lokalnih varijabli unutar opsega spoljašnjih rutina. Takvo statično gneženje se može ponoviti - funkcija deklarisana unutar funkcije deklarisane unutar funkcije ... Implementacija mora obezbediti sredstvo pomoću kojeg pozvana funkcija na bilo kojem datom nivou statičkog gnezdenja može da se odnosi na okruženje za okruženje na svakom uglađenom nivou gneženja. Uobičajeno je da se ova referenca implementira pokazivačem do okvira najnovije aktivirane instance funkcije okruženja, koja se zove "linija spuštanja" ili "statička veza", da se razlikuje od "dinamičke veze" koja se odnosi na neposrednog pozivaoca ( Koji ne trebaju biti statička roditeljska funkcija).


Umjesto statičke veze, reference na priložene statičke okvire mogu se sakupljati u niz pokazivača poznatih kao displej koji je indeksiran da locira željeni okvir. Dubina rutinskih leksičkih gnezda je poznata konstanta, tako da je veličina prikaza rutine fiksirana. Takođe, poznato je i broj sadržaja opsega za prelazak, indeks je takođe prikazan. Obično se ekran rutine nalazi u sopstvenom okviru stuba, ali je Burroughs B6500 implementirao takav prikaz u hardveru koji je podržavao do 32 nivoa statičkog gneženja.


Unosi prikaza koji sadrže opsege se dobijaju iz odgovarajućeg prefiksa prikaza pozivaoca. Unutrašnja rutina koja recursuje stvara odvojene okvire poziva za svaku poziv. U ovom slučaju, sve statičke veze unutrašnje rutine ukazuju na isti spoljašnji rutinski kontekst.


Drugo stanje vraćanja


Osim adrese za povratak, u nekim okruženjima mogu biti i druge mašine ili softverske stavke koje treba vratiti kada se potraži. Ovo može uključivati stvari kao što su nivo privilegija, informacije o iznimku, aritmetičke režime i tako dalje. Ako je potrebno, ovo se može čuvati u stomaku poziva upravo kao povratna adresa.


Tipični broj stola se koristi za povratnu adresu, lokale i parametre (poznat kao okvir poziva ). U nekim okruženjima može biti više ili manje funkcija dodeljenih u stack poziv. Na programskom jeziku Forth , na primjer, obično samo povratna adresa, računaju se parametri petlje i indeksi, a moguće i lokalne varijable se čuvaju u stack pozivu (koji se u tom okruženju naziva povratnim stekom ), mada se svi podaci mogu privremeno staviti Tamo koristi poseban kod za povratak-stack dokle se poštuju potrebe poziva i povrataka; Parametri se obično čuvaju u odvojenom stacku podataka ili u stack parametru , koji se obično naziva stack u terminologiji Forth iako postoji stack poziv jer se obično pristupa eksplicitno. Neki Forthovi imaju i treći stack za parametre sa plutajućim tačkama .

Struktura [ uredi ]

Raspored stakla poziva

Stek poziva je sastavljen od okvira stekova (takođe naziva se zapisi o aktivaciji ili okviri aktivacije ). Ovo su mašinski zavisne i ABI -ovisne strukture podataka koje sadrže podatke o podprogramu. Ovi podaci se ponekad nazivaju CFI (Call Frame Information). [1] Svaki okvir stega odgovara pozivu podprogramu koji još nije okončan sa povratkom. Na primjer, ako se potprogram Naziv DrawLine trenutno pokreće, a pozvan je podprogramom DrawSquare , gornji dio DrawSquare poziva može biti postavljen kao na slici s desne strane.

Ovakav dijagram može se nacrtati u bilo kom pravcu, sve dok se razmatra postavljanje vrha, a tako i pravac rasta stema. Štaviše, nezavisno od toga, arhitekture se razlikuju u pogledu toga da li se brojovi poziva rastu prema višim adresama ili prema nižim adresama. Logika dijagrama je nezavisna od izbora adresiranja.

Okvir stekla na vrhu stack-a je za trenutno izvršnu rutinu. Okvir stekla obično uključuje bar sledeće stavke (u redosledu pritiska):

  • Argumenti (vrijednosti parametara) prenijeti na rutinu (ako postoji);

  • Povratna adresa natrag do pozivaoca rutine (npr. U DrawLine stack okviru, adresu u DrawSquare ov kôd); I

  • Prostor za lokalne promenljive rutine (ako postoji).

Stack and frame pointers [ uredi ]

Kada se dimenzije frejmova mogu razlikovati, kao što su između različitih funkcija ili između pozivanja određene funkcije, popup kadrova iz stega ne predstavlja fiksno smanjenje pokazivaća stema . Na povratku funkcije, pokazivač stema je umesto toga vraćen na pokazivač kadra , vrednost pokazivaća stega neposredno pre pozivanja funkcije. Svaki okvir stuba sadrži pokazivač stema do vrha rama odmah ispod. Pokazivač stema je mutabilni registar deli se između svih poziva. Pokazivač frejma datog pozivanja funkcije je kopija pokazivaća stoga kao što je bilo pre nego što je funkcija bila pozvana. [2]

Lokacije svih ostalih polja u kadru mogu se definirati relativno ili na vrhu kadra, kao negativna odstupanja pokazivača stema, ili relativno u odnosu na gornji dio okvira ispod, kao pozitivna pomaka pokazivača kadra. Mesto samog pokazača frejma mora se inherentno definisati kao negativan ofset pokazivača stema.

Čuvanje adrese u okvirima pozivaoca [ uredi ]

U većini sistema okvir za stek ima polje za zadržavanje prethodne vrijednosti registra pokazivača kadra, vrijednosti koju je imao dok je pozivnik izvršavao. Na primer, okvir stacka DrawLine bi imao memorijsku lokaciju koja drži vrednost pokazivača kadra koju koristi DrawSquare (nije prikazano na dijagramu iznad). Vrednost se čuva prilikom unosa u potprogram i vraćena nakon povratka. Imajući takvo polje na poznatoj lokaciji u okviru stack-a, kôd dozvoljava pristup svakom kadru uzastopno ispod okvira trenutno izvršnog rutina, a također omogućava rutinu da lako povrati pokazivač frejma na okvir pozivaoca , neposredno prije nego što se vrati.

Leksički ugnežene rutine [ uredi ]

Dodatne informacije: Ugnežena funkcija i ne-lokalna varijabla

Programski jezici koji podržavaju ugnežene podproteje takođe imaju polje u okviru poziva koji ukazuje na okvir stacka najnovije aktivacije postupka koji najslabije obuhvata izgovaranje, tj. Neposredni opseg saziva. Ovo se zove pristupni link ili statička veza (pošto prati statičko gneženje tokom dinamičkih i rekurzivnih poziva) i pruža rutinu (kao i sve druge rutine na koje se može pozivati) pristup lokalnim podacima svojih encapsulativnih rutina pri svakom ugnjetavanju Nivo. Neke arhitekture, kompajleri ili slučajevi optimizacije čuvaju jednu vezu za svaki nivo koji se nalazi u zatvorenom prostoru (a ne samo odmah okruženje), tako da duboko ugnežene rutine koje pristupaju plitkim podacima ne moraju da prelaze nekoliko veza; Ova strategija se često naziva "prikazom". [3]

Pristupne veze se mogu optimizirati kada unutrašnja funkcija ne pristupa nekom (ne-konstantnim) lokalnim podacima u enkapsulaciji, kao što je slučaj sa čistim funkcijama koje komuniciraju samo putem argumenata i povratnih vrijednosti, na primjer. Neki istorijski računari, kao što su Burroughsovi veliki sistemi , imali su posebne "registarske oznake" za podršku ugneženih funkcija, a kompajleri za većinu savremenih mašina (kao što je sveobuhvatni x86) jednostavno rezerviše nekoliko reči u stacku za pokazivače, po potrebi.

Preklapanje [ uredi ]

Za neke svrhe, smetarski okvir podprograma i njegovog pozivaoca se može preklapati, preklapanje se sastoji od područja u kojem se parametri prenose od pozivaoca do srijede. U nekim okruženjima, pozivalac gura svaki argument na stack, čime proširuje svoj okvir stack-a, a zatim poziva pozivnika. U drugim okruženjima, pozivalac ima predodređeno područje na vrhu svog stack rama kako bi držao argumente koje on isporučuje drugim potprogramima koji pozove. Ovo područje se ponekad naziva područje odlaznih argumenata ili područje naziva. Pod ovim pristupom, veličina područja izračunava kompajler da bude najveća koja je potrebna bilo kojom pozvanom podprogramom.

Koristite [ uredite ]

Obrada lokacije poziva [ uredi ]

Obično je manipulacija stack poziva, koja je potrebna na lokaciji poziva na potprogramu, minimalna (što je dobro jer može biti mnogo lokacija za pozivanje za svaku potprogramu koja treba pozvati). Vrednosti za stvarne argumente se procenjuju na lokaciji poziva, budući da su specifične za određeni poziv i ili su gurane na stack ili stavljene u registre, kako je određeno korišćenjem konvencije za pozivanje . Stvarna uputstva za poziv, kao što su "grana i veza", se obično izvršavaju da prenose kontrolu na kod ciljne potprograma.

Obrada ulaznih podprograma [ uredi ]

U pozvanoj potprogramu, prvi izvršeni kôd se obično naziva podprogramom podprograma , pošto radi neophodno održavanje pre nego što se koda za izjave rutine počne.

Prolog će uobičajeno sačuvati povratnu adresu ostavljenu u registru pomoću instrukcije poziva pritiskom na stack poziva. Slično tome, trenutni pokazivač stoga i / ili vrijednosti pokazivača rama mogu se gurati. Alternativno, neke arhitekture setova instrukcija automatski obezbeđuju uporedivu funkcionalnost kao deo akcije same instrukcije poziva, au takvom okruženju prolog ne mora to da učini.

Ako se koriste pokazivački okvira, prolog će obično postaviti novu vrijednost registra pokazivača kadra iz pokazivaća stoga. Prostor na stacku za lokalne varijable se zatim može dodijeliti postepenim promjenom pokazivaća stema.

Forth programski jezik dozvoljava eksplicitno namotavanje stack poziva (nazvan je "povratni stack").

Obrada povratka [ uredi ]

Kada je potprogram spremna za povratak, izvršava epilog koji poništava korake prologa. Ovo će tipično vratiti sačuvane vrijednosti registra (kao što je vrijednost pokazivača kadra) iz okvira stekla, popustiti ceo okvir stacka izvan staka promjenom vrijednosti pokazivača staka i konačno grane na instrukciju na povratnoj adresi. U mnogim konvencijama koje se pozivaju predmeti predmeti poplavljeni od stega epilogom uključuju originalne vrijednosti argumenata, u tom slučaju obično ne postoje dodatne manipulacije stema koje je potrebno obaviti od strane pozivaoca. Međutim, s nekim konvencijama za pozivanje, obaveza pozivaoca je da ukloni argumente iz stega nakon povratka.

Unwinding [ uredi ]

Vraćanje iz pozvane funkcije će popustiti gornji okvir iz stega, možda ostaviti povratnu vrijednost. Općeniti čin iskočenja jednog ili više okvira izvan stakla da bi se nastavilo izvršenje na drugim mjestima u programu se zove odvijanje štaka i mora se izvesti kada se koriste ne-lokalne strukture kontrole, kao što su one koje se koriste za rukovanje izuzetkom . U ovom slučaju, okvir stema funkcije sadrži jedan ili više stavki koji specifikuju upravljačke instance izuzetaka. Kada se izbacuje izuzetak, stack se otkačuje sve dok se ne pronađe upravljač koji je spreman za rukovanje (uhvatiti) vrstu iskrivljenog izuzetka.

Neki jezici imaju druge strukture kontrole koje zahtevaju opšte odvajanje. Pascal dozvoljava globalnu izjavu za goto da prenese kontrolu iz ugnežene funkcije i u prethodno pozvani spoljašnju funkciju. Ova operacija zahtijeva da se stack otvara, uklanjajući što više okvira stekova kako bi se vratilo na odgovarajući kontekst kako bi se kontrola prenijela na ciljni izraz unutar ugrađene spoljne funkcije. Slično tome, C ima setjmp i longjmp funkcije koje deluju kao ne-lokalni goto. Common Lisp dozvoljava kontrolu nad onim što se dešava kada se štos razmnožava korišćenjem specijalnog operatora za unwind-protect vuče.

Kada se primjenjuje nastavak , stack je (logički) otkačen, a zatim se preklopi sa stekom nastavka. To nije jedini način za implementaciju nastavaka; Na primjer, korištenjem višestrukih, eksplicitnih stackova, primjena nastavka može jednostavno aktivirati svoj stack i vjetrovi vrijednost koju treba prenijeti. Programski jezik Šeme dozvoljava izvršavanje proizvoljnih mršavaka u određenim tačkama prilikom "odvijanja" ili "preopterećenja" kontrolnog stekla kada se poziva na nastavak.

Inspekcija [ uredi ]

Takođe pogledajte: Profiliranje (računarsko programiranje)

Ponekad se može proveriti da li se program pregleda. U zavisnosti od toga kako je program napisan i sastavljen, informacije o stegu se mogu koristiti za određivanje međuproizvoda i tragova poziva. Ovo se koristi za generisanje fino-zrnih automatizovanih testova, [4] iu slučajevima kao što su Ruby i Smalltalk, za implementaciju prvoklasnih nastavaka. Kao primer, GNU Debugger (GDB) implementira interaktivni pregled stack poziva u pokretanom, ali pauziranom, C programu. [5]

Uzimanje uzoraka u redovnom vremenu u stacku poziva može biti korisno u profiliranju performansi programa, jer ako se pokazivač podprograma više puta pojavi na podacima uzorka za uzorke poziva, to je verovatno kod uskog grla i treba ga pregledati za probleme sa performansama.

Bezbednost [ uredi ]

Glavni članak: Overflow buffer stack

Na jeziku sa slobodnim pokazivačem ili pismenim zapisom koji nije označen (kao u C), miješanje podataka kontrolnog toka koji utiču na izvršenje koda (povratne adrese ili ušteđeni pokazivači okvira) i jednostavni programski podaci (parametri ili povratne vrijednosti ) U stack pozivu je sigurnosni rizik, eventualno se može iskoristiti preko prekoračenja buffera stuba kao najčešći tip preloma bafera .

Jedan od takvih napada uključuje popunjavanje jednog bafera sa proizvoljnim izvršnim kodom, a zatim prelivanje istog ili nekog drugog bafera da prepisuje neku povratnu adresu sa vrijednošću koja ukazuje direktno na izvršni kod. Kao rezultat, kada se funkcija vraća, računar izvršava taj kod. Ova vrsta napada može se lako blokirati pomoću W ^ X. Slični napadi mogu uspjeti čak i uz omogućenu zaštitu od W ^ X-a, uključujući napad povratka-libc-a ili napade koji dolaze iz programa koji je orijentisan na povratak . Predložene su razne mitigacije, kao što su skladištenje nizova na potpuno odvojenoj lokaciji iz povratnog stuba, kao što je slučaj sa programskim jezikom Forth. [6]