Позивни стек

Позивни стек, у информатици, је структура стек података која чува информације о активним потпрограмима рачунарског програма. Ова врста стека је такође позната као извршни стек, стек контроле, рантајм стек или машина стека, и често скраћено као "гомила". Иако је одржавање позива стека важно за правилно функционисање већине софтвера, детаљи су обично скривени и аутоматски у програмским језицима високог нивоа. Многе рачунарске инструкције сета обезбеђују посебна упутства за манипулацију стека.

Позивни стек се користи за неколико повезаних сврха, али главни разлог је да пратите тачке у којој сваки активни потпрограм треба да врати контролу када се заврши извршавање. Активни потпрограм је онај који је позван, али тек треба да заврши извршење након чега контрола треба да се преда до тачке позива. Таква активација потпрограма може бити угњеждена на било ком нивоу (рекурзивном као посебан случај), па стек структуре. Ако, на пример, потпрограм DrawSquare позива потпрограм DrawLine из четири различита места, DrawLine мора да зна где да се врате када се извршење заврши. Да би се то постигло, адреса следеће инструкције позива, повратна адреса, је пребачена на позив стека са сваког позива.

Опис

Пошто је позивни стек организован као гомила, позивалац гура повратне адресе на стек, и под називом потпрограма, када се заврши, повуче повратне адресе изван позива стека и трансфера контроле на тој адреси. Ако се зове рутина позива на још један потпрограм, она ће гурнути још једну повратну адресу на позив стека, и тако даље, са информацијом гомилања и разлагања како програм диктира. Ако гурају, троши се сав простор издвојен за позив стека, грешка стека звана прекорачење стека, углавном узрокује да се програм сруши. Додавање улазака потпрограма за позив стека се понекад назива "навијање"; Насупрот томе, уклањање уноса се "одмотава".

Обично постоји тачно један позив стека повезан са задатим програмом (или тачније, са сваким задатком или темом процеса), иако може бити креиран додатни стек за руковање сигналима или кооперативним мултитаскингом (као и сетконтекст). Пошто постоји само један у овом важном контексту, може се назвати стек (имплицитно, "задатка") међутим, у Форт програмском језику стек података или параметар стек приступа је више експлицитан од позива стека и обично се назива стек (види доле).

У програмским језицима високог нивоа, специфичности у позиву стека су обично скривени од програмера. Они дају приступ само са сетом функција, а не меморије на самом стеку. Ово је пример апстракције. Већина језика за монтажу, с друге стране, захтевају од програмера да буду укључени у манипулацију штоса. Стварни детаљи стека у програмском језику зависе од преводиоца, оперативног система, и расположивог сета инструкција.

Функције позивног стека

Као што је већ речено, основна сврха позивног стека је да складишти повратне адресе. Када се потпрограм зове, локација (адреса) за наставу на којима се касније могу наставити потребна је да се негде сачувана. Коришћење стека да сачувате повратне адресе има значајне предности у односу на алтернативне конвенције позивања. Једна је да сваки задатак има свој стек, а самим тим и потпрограм може бити увучен, односно, могу бити активни истовремено за различите задатке да обављају различите ствари. Још једна предност је да је рекурзија аутоматски подржана. Када функција себе саму позива рекурзивно, повратна адреса треба складиштити свако активирање функције тако да се касније може користити за враћање из активације функције. Ова могућност је аутоматски са стека.

Позивни стек може послужити у додатне сврхе, у зависности од језика, оперативног система и машина животне средине. Међу њима могу бити:

Локално складиштење података

Потпрограму често треба меморијски простор за чување вредности локалних променљивих, променљиве које су познате само у активном потпрограму и не задржавају вредности када се враћају. Често је обичај да се издвоји простор за њихово коришћење једноставним померањем врха гомиле од стране довољно да се обезбеди простор. Ово је врло брзо у односу на динамичку расподелу меморије, који користи гомилу простора. Имајте на уму да свако одвојено активирање потпрограма добија свој посебан простор у стеку за локале.

Параметар доношења

Потпрограми често захтевају да се вредности за параметре доставе од стране кода који их позива, а није редак случај да простор за ове параметре може бити постављена у позивном стеку. Генерално, ако постоји само неколико малих параметара, процесор регистра ће се користити да прођу вредности, али ако постоји више параметара него што се може руковати на овај начин, меморијски простор ће бити потребан. Позивни стек ради добро као место за ове параметре, нарочито јер сваки позив за потпрограме, који ће имати различите вредности за параметре, добиће посебан простор на позивном стеку за те вредности.

Евалуација стека

Операнди за аритметичке или логичке операције се најчешће стављају у регистре и раде тамо. Међутим, у неким ситуацијама операнди могу бити сложени до произвољне дубине, што значи нешто више него што регистри морају да користе (то је случај регистра расподеле). Стек таквих операнада, а као да је у ОПН калкулатору, се назива стек евалуације, а могу да заузимају простор и у позивном стеку.

Показивач тренутне инстанце

Неки објектно оријентисани језици (нпр С++), чувају овај показивач са функцијом аргумената у позивном стеку када позивају методе. Овај показивач указује на објекат инстанце у вези са методом где ће се позивати.

Закључивање контекста потпрограма

Неки програмски језици (нпр, Паскал и Ада) подржавају уметнуте потпрограме, омогућавајући унутрашњој рутини приступ контексту његове спољне окружене рутине, односно параметара и локалних променљивих у оквиру спољашње рутине. Таква статична угнежђења могу да понављају - функцију проглашену у функцији проглашеној у функцији ... Имплементација мора да обезбеди средства којима се зове функција у сваком статичком нивоу угнежђеном помоћу референци прихватног оквира на сваком нивоу прихватног гнезда. Обично та референца спроводи показивач на свеобухватном оквиру, који се зове "доњи стек линк" или "статична веза", да би се разликовало од "динамичког линка" која се односи на непосредног позиваоца (што не мора бити функција родитеља) . На пример, језици често дозвољавају унутрашњој рутини да се рекурзивно позове, што је резултирало вишеструким оквирима позива за призивање унутрашње рутине, сви чије статичке везе указују на исте спољашње рутинске контексте. Уместо статичког линка, референце на прихватним статичким оквирима могу да буду наплаћене у низ показивача познатих као екран који је индексиран да лоцира жељени оквир. Burroughs огромни системи су имали такав екран у хардверу који је подржавао до 32 нивоа статичког гниезда.

Друго повратно стање

Поред повратне адресе, у неким срединама могу постојати друге машине или софтвери који наводе да треба да се врати када је потпрограм повратан. Ово може укључивати ствари као што су нивои привилегија, изузетак руковања информацијама, аритметичког режима, и тако даље. Ако је потребно, то може да се чува на позивном стеку као повратна адреса.

Типичан позивни стек се користи за повратну адресу, локала и параметара (познат је као позивни оквир). У неким срединама може бити више или мање функција које су позивни стек. У Форт програмском језику, на пример, обично само повратна адреса, рачунајући параметре и индексе петље, а евентуално локалне променљиве су сачуване на позивни стек (која је у том окружењу и која се зове повратни стек), мада неки подаци могу бити привремено постављени не помоћу посебног повратног стека руковања кода толико дуго као потреба позива и повратка које се поштују; параметри се обично чувају на одвојеном стеку података или параметара стека и обично се назива штос у Форт терминологији иако се позиву стека обично приступа више експлицитно. Неки Фортови имају и трећу хрпу за померајуће тачке параметара.

Структура

Изглед позивног стека

Позивни стек се састоји од оквира стека (такође познатог као активација евиденције или активација оквира). То су зависне машине и ABI-зависне структуре података које садрже информације о стању потпрограма. Ови подаци се понекад називају и CFI (позивни рам информација). ^[1] Сваки оквир стека одговара позиву потпрограмима који још нису престали са повратком. На пример, ако потпрограм по имену DrawLine тренутно ради, пошто је позвао потпрограм DrawSquare, горњи део позивног стека може бити постављен као на слици на десној страни.

Дијаграм се овако може извући у оба смера док је пласман у врху, по смеру раста стека, подразумева се. Осим тога, независно од тога, архитектуре разликују око тога да ли позив стека расте ка вишој адреси или ка нижој адреси. Логика дијаграма је независна од адресирања избора.

Стек оквира на врху гомиле је за тренутно извршавање рутине. Стек оквира обично укључује најмање следеће ставке (у редоследу):

аргументи (вредности параметара) донети на рутину (ако их има)
повратна адреса ће се вратити саговорнику рутине (нпр у DrawLine стек оквиру, адресе у DrawSquare кода) и
простор за локалне променљиве у рутину (ако их има).

Стек и показивачи оквира

Када величине стек оквира могу да се разликују, као што је између различитих функција или између призивања одређене функције, искакање оквира са стека и то не представља фиксно смањење показивача стека. У функцији повратка, стек показивач уместо да врати оквир показивача, вредност стек показивача непосредно пре функција је названа. Сваки стек оквир садржи стек показивач на врху оквира одмах испод. Стек показивач је променљиви регистар који се дели између свих призива. Оквир казаљка датог позивања на функције је копија стека показивача јер је пре него што је функција позвана.^[2]

Локације свих других области у оквиру могу бити дефинисане у односу на врх оквира, као компензација негативног стека показивача, или у односу на врх оквира испод, као позитивне компензације оквира показивача. Положај оквира сам по себи мора бити дефинисан као негативна компензација стека показивача.

Чување адресу на оквиру позиваоца

У већини система стек оквир мора да садржи поље претходне вредности оквира показивача регистра, вредност коју је имао док се саговорник извршавао. На пример, стек оквира DrawLine ће имати меморијску локацију која држи показивач вредности оквира који DrawSquare користи (које нису приказане у дијаграму горе). Вредност је спашена након уласка у потпрограм и обновљена након повратка. Имајући такву област у познатој локацији у оквиру стека омогућава код за приступ сваком оквиру сукцесивно испод оквира у тренутној извршаваној рутини, а такође омогућава рутини да лако врати оквирни показивач на оквир позиваоца, непосредно пред враћања.

Лексички угнежђене рутине

Додатна литература: Угнежђена фунцкија и Не-локална променљива

Програмски језици који подржавају угнежђене потпрограме такође имају поље у оквиру позива који упућују на стек оквир најновије активирање процедуре која најприближније инкапсулира позвани, односно непосредни оквир позваног. То се зове веза приступа или статична веза (као што прати статичко гнездо у динамикним и рекурзивним позивима) и даје рутину (као и било које друге рутине које могу да се позову) приступ локалним подацима својих инкапсулираним рутинама у сваком угнежђеном нивоу. Неке архитектуре, преводиоци, или случајеви оптимизација неког линка за сваки ниво, тако да је дубоко угнежђене рутине које приступају плитким подацима не морају да пролазе неколико линкова; ова стратегија се често назива "екран".^[3]

Приступни линкови могу бити оптимизовани далеко када се унутрашњој функцији не може приступати (није константа) локалним подацима, као што је то случај са чистим функцијама које комуницирају само путем аргумената и повратних вредности, на пример. Неки историјски рачунари, као што су Burroughs великих система, имали посебне "регистре екрана" да подржи угнежђене функције, док компајлери НА најсавременијим машинама (као што су свеприсутне x86) једноставно задржавају неколико речи на стеку за показиваче, по потреби.

Преклапање

За неке сврхе, стек оквира од потпрограма и од свог саговорника може се сматрати да се преклапају, преклапање се састоји од подручја где се доносе параметри од саговорника. У неким срединама, саговорник гура сваки аргумент на стек, чиме продужава свој стек оквир, а затим призива позвани. У другим срединама, позивалац има простор на врху свог стек оквира да држи аргументе које снабдева са другим потпрограмима. Ово подручје се понекад назива област одлазног аргумената или. Према овом приступу, величина простора се обрачунава по компајлеру да је то највећа потребна било која позвана од стране потпорграма.

Примена

Позив за обраду положаја

Обично је позив стек манипулације потребно на месту позива потпрограма (што је добро, јер не може бити много положаја позива за сваки потпрограм да се зове). Вредности стварних аргумената се процењују на позив положаја, јер су специфичне за одређени позив, као што је одређено конвенцијом. Стварна инструкција позива, као што су "гране и линк", онда се обично извршавају тако да пренесу контролу кода циљаног потпрограма.

Потпрограм за обраду уноса

У позованом потпрограму, први код извршавања се обично назива потпрограм пролога, јер ради неопходно поспремање кода за изјаве рутине која је почела.

Пролог ће обично сачувати повратну адресу лево у регистру од стране инструкција позива гурањем вредности на позивни стек. Слично томе, садашњи стек показивач и / или оквир показивача вредности могу бити гурнути. Алтернативно, неки сет инструкција архитектуре аутоматски даје поредити функционалност као део акције инструкције која позива саму себе, а у таквом окружењу пролог се не мора урадити.

Ако се користе оквири показивача, пролог ће обично поставити нову вредност оквира показивача регистра са стека показивача. Простор на стек за локалне променљиве се онда може издвојити постепено како се мења стек показивача.

Форт програмски језик дозвољава експлицитно намотавање позивног стека (тзв. "повратни стек").

Повратна обрада

Када је потпрограм спреман да се врати, она извршава епилог који опозива кораке пролога. Ово ће обично повратити сачуване вредности регистра (као оквир показивача вредности) из стека оквира, и на крају грана на упутству на повратну адресу. У многим позивањима конвенција ставке је пукла што је епилог укључивања оригиналног аргумента вредности. Са неким позивањем конвенција, међутим, даје се одговорност саговорника да уклони аргументе из стека након повратка.

Одмотавање

Враћајући се од стране позване функције која ће се појавити на врху оквира са стека, можда остављајући повратну вредност. Што више општих акта искакања једног или више оквира са гомиле да наставе извршење на другом месту у програму који се зове стек одмотавања и мора се извршити када се користе нелокалне контролне структуре, као што су они који се користе за коришћење изузецима. У том случају, стек оквир функција садржи један или више улазака које одређују изузетак. Када је бачен изузетак, стек се одмотава да се утврди да ли је спреман за коришћење.

Неки језици имају и друге контролне структуре које захтевају одмотавање. Паскал омогућава глобални GoTo изјаву да пренесе контролу из функције и у претходно позваној спољној функцији. Ова операција захтева да се одмотава стек, уклања онолико стек оквира неопходних да се обнови одговарајући контекст како би се пренела контрола на циљну изјаву у прихватној спољашњој функцији. Слично томе, С има setjmp и longjmp функције које делују као нелокални GoTo. Common Lisp омогућава контролу над оним што се дешава када се одмотава стек помоћуunwind-protect посебног оператера.

Приликом подношења захтева за наставак, стек се (логично) одмотава, а потом замотава са гомиле наставка. Ово није једини начин за спровођење наставка; на пример, користећи више, експлицитне гомиле, примена наставка може једноставно активирати свој стек и вредност да буде усвојена. Scheme програмски језик дозвољава произвољно да се изврши у одређеним тачкама на "одмотавању" или "премотавању" у контролном стеку када се покрене процедура за наставак.

Преглед

Види још: Профилисање (рачунарство) и Дубоко узорковање

Позивни стек може понекад бити прегледан као програм извршавања. У зависности од тога како је програм написан и састављен, информације о стеку могу да се користе за одређивање међурезултата и трагова функције позива. Ово се користи за генерисање фине структуре аутоматских тестова,^[4] и у случајевима као што су Руби и Smalltalk, да спроведу првокласне наставке. Као пример, ГНУ дибагер (ГДБ) спроводи интерактивни увид у позивни стек једног позива, али је застао, С програм.^[5]

Узимајући редовно радно време узорка из позивног стека може бити корисно у профилисању перформанси програма, јер ако се показивач потпрограма појављује на позивном стеку узорковања података много пута, вероватно је шифра уског грла и треба проверавати за проблеме перформанси.

Безбедност

Главни чланак: Стек бафера преливања

У језику са слободним показивачима или непровереним низом пише (као у С), мешање података контроле протока утиче на извршење кода (враћа адресе или сачуване оквире показивача) и једноставне податке програма (параметре или повратне вредности) у позивном стеку и то је безбедносни ризик, могуће је експлоатисати преко стека бафера преливања као најчешћи тип бафера преливања.

Један од таквих напада подразумева пуњење једног бафера са произвољним извршним кодом, а затим преливање истог или неки другог бафера да препише неку повратну адресу са вредношћу која указује директно на извршни код. Као резултат тога, када се функција враћа, рачунар извршава тај код. Ова врста напада се може лако блокирати W^X. Слични напади могу успети чак и са W^X омогућеном заштитом, укључујући и повратни напад компајлер или напада повратно оријентисаног програмирања. Разна ублажавања су предложена, као што је складиштење низова у потпуно одвојеној локацији од повратног стека, као што је то случај у Форт програмском језику.^[6]

Види још

Референце

^ Nicholas Carlini and David Wagner.
^ "Understanding the Stack". cs.umd.edu. 2003-06-22.
^ Alternative Microprocessor Design
^ McMaster, S.; Memon, A. (2006).
^ "Debugging with GDB: Examining the Stack" Архивирано на сајту Wayback Machine (14. април 2021). chemie.fu-berlin.de. 1997-10-17.
^ Doug Hoyte.

Литература

Dijkstra, E. W. (1960). „Recursive Programming”. Numerische Mathematik. 2: 312—318. S2CID 60570038. doi:10.1007/BF01386232.
Wilson, P. R.; Johnstone, M. S.; Neely, M.; Boles, D. (1995). „Dynamic Storage Allocation: A Survey and Critical Review”. Memory Management. Lecture Notes in Computer Science. 986. стр. 1—116. CiteSeerX 10.1.1.47.275  . ISBN 978-3-540-60368-9. S2CID 9937761. doi:10.1007/3-540-60368-9.

Спољашње везе

Function Calling and Frame Pointer Operations in 68000 Архивирано на сајту Wayback Machine (24. јул 2010)
The libunwind project - независна платформа API

[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" Архивирано на сајту Wayback Machine (14. април 2021). chemie.fu-berlin.de. 1997-10-17.

[6] Doug Hoyte.

[1]

[2]

[3]

[4]

[5]

[6]