Kutsepinu: kaadrid, tagastusaadressid ja ületäitumine

Funktsioonikutse teeb mällu mõned kirjutused. Naasmisel loetakse mälust aadress ja hüpatakse sinna. Käivita mõnda neist neljast väikesest programmist sammhaaval ja jälgi pinu, mille suurim aadress on ülal. Kirjutused on merevaigukollased, lugemised sinised. Eemaldatud kaadri pesad jäävad tuhmimalt nähtavale, sest nende sisu pole kustutatud.

Näidisarvutus — Kutsepinu: kaadrid, tagastusaadressid ja ületäitumine

Kutsete arv	5
Suurim sügavus kaadrites	5
Pinukasutus suurimal sügavusel	60 baiti 128 baidist
Tulemus	120

Need on väärtused, mida kalkulaator lehe avamisel näitab. Muuda ülal mõnda sisendit, et need ümber arvutada.

Interaktiivse simulatsiooni laadimine...

Õppetund

Teooria — Kutsepinu: kaadrid, tagastusaadressid ja ületäitumine

Kutsepinu on mälupiirkond, kus iga funktsioonikutse saab oma kaadri. Siin sisaldab see argumenti, tagastusaadressi ehk kohta, kust väljakutsuja jätkab, väljakutsuja salvestatud kaadriviita ja kohalikke muutujaid. Pinuviit näitab väikseimat kasutusel olevat aadressi. Kutse liigutab seda ühe kaadri võrra allapoole, naasmine tagasi ülespoole. Kui rekursiooni sügavus on d kutset ja iga kaader võtab f baiti, kulub pinus d·f baiti.

Mida iga sümbol tähendab

d: sügavus: korraga pinus olevate kaadrite arv
f: ühe kaadri suurus baitides: siin 12, lisaks 4 iga kohaliku muutuja kohta

Eeldab: 32-bitine masin klassikalise C kutsekonventsiooniga: 4-baidised pesad, väiksemate aadresside poole kasvav pinu, pinus edastatavad argumendid ja igas kaadris säilitatav kaadriviit. Tegelikud 64-bitised kutsekonventsioonid edastavad esimesed argumendid registrites ja kompilaatorid võivad kaadriviida ära jätta. ARM-il võib funktsioon, mis ise midagi välja ei kutsu, hoida tagastusaadressi registris. Seetõttu erinevad tegelike kaadrite suurus ja paigutus siin näidatud kolmest pesast.

Tagastusaadress on arv mälus ja massiiv võib selle üle kirjutada 🖖

Vajuta nuppu Kuus väärtust nelja. Funktsiooni copy massiivis buf on ruumi neljale int-tüüpi väärtusele. buf[0] asub väikseimal aadressil, nii et buf[4] ja buf[5] on lihtsalt kaks järgmist pesa suuremate aadresside poole. Kutse paigutas sinna salvestatud kaadriviida ja selle järele tagastusaadressi. Tsükkel indeksit ei kontrolli. Viies väärtus asendab kaadriviida ning kuues, 0x46464646, tagastusaadressi. Kui copy naaseb, loeb protsessor sellest pesast aadressi ja hüppab sinna. Nelja väärtuse korral naaseb copy õigesti aadressile 0x08048400. Viie korral naaseb see ikka samasse kohta, kuid annab mainile tagasi rikutud kaadriviida. Seda nimetatakse pinupuhvri ületäitumiseks. Novembris 1988 tungis Morrise uss sel viisil programmi fingerd: fingerd luges sisendi 512-baidisesse puhvrisse, piiramata loetava sisendi pikkust.

Väärtustamata muutujasse jääb see, mille eelmine kutse sinna jättis 🖖

Vajuta nuppu Alles jäänud väärtus. set kirjutab oma kohalikku muutujasse 42 ja naaseb. Naasmine liigutab pinuviita ülespoole, kuid ei kustuta midagi. Seejärel kutsutakse samast kohast välja peek, mille kaader paigutub samadele aadressidele. Selle kohalik muutuja y asub aadressil 1008, täpselt seal, kus enne oli x. peek ei kirjuta muutujasse y midagi, nii et selle lugemisel saadakse 42. C keeles on algväärtustamata muutuja lugemine määratlemata käitumine: keel ei taga tulemust ning optimeeriv kompilaator võib selle pesa lugemise üldse ära jätta. Kui lugemine siiski toimub, leitakse sealt väärtus, mis sinna viimati kirjutati.

Pinus on üks kutseahel 🖖

Sea fib-i argumendiks 10. Tehakse 177 kutset, kuid suurimal sügavusel on pinus 10 kaadrit ehk 120 baiti. Ühe kutse kaader eemaldatakse enne, kui lisatakse sama taseme järgmise kutse oma. Nii sisaldab pinu ainult ahelat fib(10)-st parajasti täidetava kutseni. fact(11) teeb 11 kutset, umbes kuueteistkümnendiku sellest arvust, kuid põhjustab pinu ületäitumise: selle ahel on 11 kaadrit pikk ja vajab 132 baiti. Kummaski funktsioonis teeb iga kutse peale rekursiivsete kutsete kindla hulga tööd. Seetõttu iseloomustab kutsete arv ajakulu ja pikima ahela sügavus pinukasutust.

Ülesanne täielikult lahendatud

Kui sügavale saab rekursioon minna? 4 sammu
Vajuta nuppu fact(11): ületäitumine. Selle lehe pinu mahutab 128 baiti. Microsofti linkur eraldab programmile vaikimisi 1 MB pinu. Võtame selleks 1 MiB ehk 1 048 576 baiti ja kasutame siinseid kaadreid. Kui sügavale saab fact minna? Kui sügavale siis, kui igal kutsel on ka üks 4-baidine kohalik muutuja? Kui palju pinu vajab fib(30) ja mitu kutset see teeb?

Ava see ülesanne tööriistas
1. Siinne kaader koosneb argumendist, tagastusaadressist ja salvestatud kaadriviidast: 3 × 4 = 12 baiti. 128 / 12 = 10,67, seega mahub pinusse 10 kaadrit. fact(11) vajab 11 × 12 = 132 baiti. Tulemuste tabel näitab ületäitumist.
  
  $f = 3 \times 4 = 12, ⌊ \frac{128}{12} ⌋ = 10, 11 \times 12 = 132 > 128$
2. 1 048 576 / 12 = 87 381,33, seega mahub pinusse 87 381 kaadrit. fact saaks jõuda 87 381 rekursioonitasemeni, enne kui pinuruum otsa lõpeb. Vastus ületab 32-bitise int-tüübi piiri juba palju varem: 13! = 6 227 020 800.
  
  $⌊ \frac{1 048 576}{12} ⌋ = 87381$
3. Ühe 4-baidise kohaliku muutujaga võtab iga kaader 16 baiti ning 1 048 576 / 16 = 65 536 täpselt.
  
  $f = 16 : \frac{1 048 576}{16} = 65536$
4. fib(30) pikimas ahelas on 30 kaadrit: 30 × 12 = 360 baiti. Kutsete arv on 2·F(31) − 1, kus F(31) = 1 346 269 on 31. Fibonacci arv. Kokku tehakse 2 692 537 kutset.
  
  $d = 30 : 30 \times 12 = 360, 2 F_{31} - 1 = 2 \times 1346269 - 1 = 2692537$
Vastus

87 381 taset või ühe kohaliku muutujaga 65 536. fib(30) vajab 2 692 537 kutse tegemiseks 360 baiti pinu. Sügavus määrab pinukasutuse; fib-i puhul määrab kutsete arv ajakulu.

$d_{m a x} = ⌊ \frac{S}{f} ⌋ = 87381 (f = 12), 65536 (f = 16)$

Õpitee

Kuidas arvuti programmi täidab

Allikad (2)

The worked problem's stack size: the linker's default reservation: Microsoft Learn, "/STACK (Stack allocations)," C/C++ build reference, updated 23 February 2022.
The first insight's 1988 example: fingerd's unbounded read into a 512-byte buffer on the stack: Bob Page, "A Report on the Internet Worm." University of Lowell, 7 November 1988 (copy hosted at Toronto Metropolitan University).

42Mathi meeskond · Kontrollitud avaldatud allikate põhjal. Parandused on teretulnud.