Ohjelman jälki sekä pinokehyksen synty ja tuho

ITKA203 Käyttöjärjestelmät -kurssin Demo 5 keväällä 2015 ja 2016 ja 2017 ja 2018 ja 2019 ja 2020 ja 2021 ja 2022 ja 2023. "Ohjelman jälki sekä pinokehyksen synty ja tuho" - Kevyt katsanto ohjelman konekieliseen jälkeen.

Paavo Nieminen, paavo.j.nieminen@jyu.fi

STATUS: Tehtävänanto on aika stabiilissa kunnossa jo vuosia. Ilmoita mahdollisista ongelmista, niin korjataan, mitä tarpeen on!

Sisällys

Tämän harjoituksen tavoitteet

Päätavoite:

  • Näet esimerkin kautta, kuinka konekielinen ohjelma saa prosessorin suorittamaan aliohjelma-aktivaation. Sisäistät suorituspinon toimintaperiaatteen ja roolin prosessin (tai säikeen) suorituksessa.

Toissijainen tavoite:

  • samalla näet hieman yleiskuvaa konekielisestä ohjelmoinnista.
  • samalla syvennyt viitteen (tai muistiosoittimen) rooliin ohjelmoinnissa, mikä parantaa yleistä kykyäsi ymmärtää ohjelmia.

Historiallisia huomautuksia: Aliohjelma-aktivaation toimintaa käsittelevä harjoitustyö tai laajempi demo on ollut mukana käyttöjärjestelmäkurssilla IT-tiedekunnan perustamisesta alkaen, ja vuosia sitäkin ennen. Perinne jatkuu, mutta harjoituksen pakollista osuutta on pienennetty, ja taustoja on nyt käyty läpi kurssin alusta saakka luennoilla ja monisteessa.

Käytämme vuonna 2023 relevantteja työkaluja, joita kurssin luennoilla on alusta lähtien esitelty eli x86-64 -arkkitehtuurin mukaisissa Red Hat Enterprise Linux -virtuaalipalvelimissamme toimivaa C-kääntäjää gcc sekä debuggeria gdb. C-kääntäjää ajetaan komennolla c99, jolloin se toimii uusimman POSIXin käyttämän C99-standardin mukaisesti (tilanne tarkistettu POSIX-version suhteen viimeksi 3.5.2023).

Vastaava harjoitus voitaisiin tehdä yksinkertaisella "lasten tietokonesimulaattorilla" tai jonkin muinoisen (ja sitä kautta nykyisiä yksinkertaisemman) prosessorin emulaattorilla, mutta kirjoittaja on sitä mieltä, että nykyisen tuotantovälineistön käyttö tarjoaa jonkinlaisen "oikotien onneen": Oppimiskynnys voi olla jyrkempi kuin lelulla leikittäessä, mutta kaikki työ tehdään kohti todellisia taitoja ja jokaisella käytännön yksityiskohdalla on merkitystä tämän päivän maailmassa.

Yhteisen palvelimen käyttö mahdollistaa tässäkin demossa yhtenäisen ohjeistuksen laitteistoon ja ohjelmistoon, mikä ei mikroluokkia ja kotikoneita käytettäessä välttämättä olisi järin helppoa.

Minimaalinen pakollinen osuus

Valmistele hakemisto tätä demoa varten ja hae pieni koodipaketti seuraavin komennoin:

wget https://gitlab.jyu.fi/itka203-kurssimateriaali/itka203-kurssimateriaali-avoin/-/raw/master/2015/demot/mallikoodia/d05/d05_paketti.zip
unzip d05_paketti.zip

Tutustu mukana olevaan C-kieliseen ohjelmaan malliharkka.c. Mukana on Makefile, joka automatisoi vaiheita. Seuraava komento kääntää ja suorittaa ohjelman tulosteiden kanssa:

make kokeile

Seuraava komento ajaa ohjelmasta osan gdb-debuggerissa konekielikäsky kerrallaan ja tallentaa loki.txt -nimiseen tiedostoon kiinnostavia tulosteita jokaisen käskyn jälkeen:

make loki.txt

Seuraava komento ajaa hassun skriptin selaa_tulostetta.sh, jolla lokiin kirjattua jälkeä voi selata edestakaisin:

make selaile

(Kiinnostuneet sielut voivat tutkia, miten selailuskripti on tehty... Pääosin POSIX-yhteensopiva, mutta yhden merkin lukeminen terminaalista ei ole standardin piirissä, vaan mukavuussyistä se on nyt jotain mikä sattuu toimimaan käytössämme olevassa palvelinympäristössä tällä hetkellä.)

Tavoite on tutkia asiaa, kunnes pystyt täydentämään kaikkien tiedostossa d05_vastaus.txt kysyttyjen kysymysten vastaukset tiedostoon. Palautuslaatikkoon laitetaan vastauksin täydennetty tiedosto.

Seuraavien asioiden tarkastelu kuuluu pakolliseen osioon:

Vapaaehtoista lisätekemistä, osa I

Ja vapaaehtoisesti voi halutessaan pyrkiä syventämään ymmärrystään katsomalla myös, miten silmukan alkuarvot asetetaan, miten lopetusehto tarkastetaan, miten silmukan alkuun hypätään joka kierroksella ym.

Vapaaehtoista lisätekemistä, osa II

Tässä hieman avataan vaiheita, jotka Makefile ja gdb-skripti tekevät automaattisesti. Saa lukea läpi, kokeilla manuaalisesti rivi riviltä jne.

Alustava esimerkki: ohjelma x86-64 -assembleriksi GNU-kääntäjällä (gcc)

Demon ohjelma on nimeltään malliharkka.c, koska aiempina vuosina on tehty laajempi työ, jonka malliesimerkki tämä kyseinen koodi oli. Ajat muuttuvat, ja kurssit helpottuvat...

Ohjelmassa on oikeastaan kaksi versiota, jotka valitaan esikääntäjän makron avulla: oletuksena ohjelma ainoastaan laskee tulostamatta mitään. Tällä tavoin ei siis näy paljon tuloksia (saa kokeilla):

gcc malliharkka.c
./a.out

Kokeile huvikseen seuraavaa:

gcc -E malliharkka.c | less

Em. komennolla ajoit vain C-käännöksen ensimmäisen vaiheen, jossa ns. esikääntäjä lisäilee omia rivejään lähdekoodiin, käsittelee mm. #include -rivit sekä myös #ifdef ja #ifndef ynnä muut direktiivit. Tulostukseen liittyvät koodin osat eivät ole mukana käännöksen seuraavissa vaiheissa, ellei niitä erikseen pyydä sinne. Makron TEE_TULOSTEET voi laittaa päälle kääntäjän optiona seuraavasti:

gcc -DTEE_TULOSTEET malliharkka.c
./a.out

Tällä tavoin ohjelma tulostaa. Voit myös verifioida, että esikääntäjä ottaa tällöin mukaan paljonkin enemmän C-koodia kuin ilman kyseistä asetusta:

gcc -E -DTEE_TULOSTEET malliharkka.c | less

Makefilessa makro asetetaan yhden kohteen käännöksessä, mutta harjoitukseen liittyvää lokia varten tulostuskutsuja ei haluta.

Katsotaan sitten yleiskuvaa assembler-kielisestä käännöksestä. Anna seuraava komento:

gcc -O0 -S malliharkka.c

Optio -O0 (eli iso oo ja nolla) on vanha tuttu. Se pyytää, että kääntäjä ei optimoisi koodia. Koodin optimointi oletettavasti tekisi käännöksestä vaikeamman ymmärtää, kun tuotettu konekieli koettaisi oikoa mutkia suoriksi nopeamman suoritettavuuden ja/tai lyhyemmän binääritiedoston toivossa. Optio -S (eli iso äs) tarkoitti, että ei käännetä valmiiksi konekieleksi asti, vaan tuotetaan vastaava assembler-koodi. Nyt pitäisi olla syntynyt tiedosto malliharkka.s. Sen pitäisi alkaa jotakuinkin näin:

.
      .file   "malliharkka.c"
      .text
      .globl sakkokierros
      .type   sakkokierros, @function
sakkokierros:
.LFB0:
      .cfi_startproc
      pushq   %rbp
      .cfi_def_cfa_offset 16
      .cfi_offset 6, -16
      movq    %rsp, %rbp

...

Pisteellä alkavat tekstit ovat assemblerin omia ohjauskomentoja. Esimerkiksi .file "malliharkka.c" kertoo, että tämä on syntynyt tuon nimisestä C-koodista kääntämällä. .text kertoo, että seuraavat asiat pitää sijoittaa koodialueelle (jota sanotaan jostain syystä tekstialueeksi Unix-maailmassa...) .globl symboli tarkoittaa että meillä on globaali symboli nimeltä symboli ja .type symboli, @function kertonee että kyseinen symboli tarkoittaa funktiota eli aliohjelmaa.

Kaksoispisteeseen päättyvät rivit ovat symbolisia nimiä muistiosoitteille. Eli sekä sakkokierros että .LFB0 ovat nimiä sille muistipaikalle, jossa sijaitsee käskyn pushq %rbp konekielikoodin ensimmäinen tavu. Assembler-ohjelmoijan ei tarvitse tietää muistipaikan numeroarvoa; itse asiassa voi olla, että kukaan ei tiedä lopullisia osoitteita ennen kuin käyttöjärjestelmä lataa konekielisen ohjelman kovalevyltä muistiin suoritusta varten.

Halutessasi tutustu lyhyesti assembler-käännökseen, pyri alustavasti ymmärtämään, miten se toimii. Luentomateriaalissa on x86-64 -assemblerin esimerkkikäskyjä. Sieltä pitäisi tutunnäköisiä käskyjä löytyä. Tämän näköisenä ohjelma ilmenee aivan viimeisessä käännösvaiheessa.

GNU-debugger (gdb) ja tilannetiedon tulosteet

Debuggausta varten käännä ohjelma komennolla:

gcc -g -O0 -o malliharkka malliharkka.c

Vastaavaa kokeiltiin alustavasti jo demossa 3. Argumentti -g tuottaa debug-tiedot, joiden avulla debuggeri osaa liittää tulosteisiinsa lähdekooditiedostoissa esiintyvät rivinumerot ja symbolien nimet. Pitäisi syntyä ajettava konekielinen tiedosto malliharkka.

Käynnistä komentorividebuggeri demo 3:n tyyliin seuraavasti:

gdb malliharkka

Debuggeria voi nyt komentaa tekstillä. Peruskomentoja, joita kurssilla on tähän mennessä nähty luennoilla ja demoissa:

run      käynnistää ja suorittaa, kunnes tulee jokin tarve pysähtyä
help     antaa ohjeita
quit     lopettaa debuggerin

disassemble     näyttää konekielikoodin disassemblynä
backtrace       näyttää kutsupinon tilanteen
info registers  näyttää prosessorin rekisterien tilanteen
x               näyttää muistin sisältöä osoitteen perusteella
                (tarvitsee apuja muistin sisällön tulkinnan suhteen;
                "help x" näyttää apuja.)

start    käynnistää ja suorittaa, kunnes main() -aliohjelma alkaa
step     askeltaa lähdekoodirivin kerrallaan
stepi    askeltaa konekielikäskyn kerrallaan
finish   suorittaa pinon päällimmäisen aliohjelma-aktivaation loppuun

Katsotaan sitten komentoja, joilla saa automaattisia tulosteita aina käskyn suorituksen jälkeen:

display /3i $rip
display /t $eflags
display /x $rbp
display /x $rsp
display /x $rip

Voit copy-pastata suoraan tästä harkkaohjeesta. Komennot voi halutessaan lukea tiedostosta gdb:n käynnistyksen yhteydessä optiolla -x aloituskomentoja.esim. Ylläolevien komentojen merkitys on, että tästedes gdb näyttää aina automaattisesti seuraavat tiedot (viimeksi komennettu ensimmäisenä):

/x $rip käskyosoiterekisterin arvo heksalukuna ("x = hex"), seuraavaksi suoritettava konekielikomento tullaan noutamaan (fetch) tästä muistiosoitteesta
/x $rsp pino-osoittimen arvo heksalukuna
/x $rbp pinokehyksen kantaosoittimen arvo heksana
/t $eflags lippurekisterin lippubitit ("t = base two l. bitit")
/3i $rip kolme konekielikäskyä alkaen muistipaikasta, johon RIP osoittaa ("3i = three instructions")

Jos tuli kirjoitus- tai kopiointivirhe, voit komentaa undisplay, mikä poistaa aiemmat näyttövalinnat, ja sen jälkeen voi antaa uudelleen ylläolevat (tai muut sopivat) display -komennot. Ne jäävät voimaan seuraavaan undisplayhin asti.

Esimerkiksi voit nyt käynnistää ohjelman, ja todeta, että pyydetyt tiedot tulostuvat:

start

Pitäisi olla jotakin seuraavanlaista:

Temporary breakpoint 1 at 0x400606: file malliharkka.c, line 69.
Starting program: /autohome/home3/363/nieminen/files/kjesim/malliharkka/malliharkka
warning: no loadable sections found in added symbol-file system-supplied DSO at 0x2aaaaaaab000

Temporary breakpoint 1, main (argc=1, argv=0x7fffffffe208) at malliharkka.c:69
69        long long int testitaulu[] = {-1, 2, 3, -16, 2, 8};
5: /x $rip = 0x400606
4: /x $rsp = 0x7fffffffe0d0
3: /x $rbp = 0x7fffffffe120
2: /t $eflags = 1000000010
1: x/3i $rip
0x400606 <main+15>:     movq   $0xffffffffffffffff,-0x40(%rbp)
0x40060e <main+23>:     movq   $0x2,-0x38(%rbp)
0x400616 <main+31>:     movq   $0x3,-0x30(%rbp)

Koska käännöksessä oli mukana debug-tiedon tallennus ja lähdekoodi on saatavilla, debuggeri kykenee näyttämään C-kielisen koodirivin, jota ollaan suorittamassa. Sitten näkyvät edellisissä display-komennoissa pyydetyt asiat.

Debuggerin saa käskettyä näyttämään automaattisesti muitakin virheenkorjauksessa tarvittavia tietoja, joiden muutoksia voidaan tarkkailla lähelle ongelman ilmenemiskohtaa sijoitetun breakpointin jälkeen. Tässä siis oli vain perusidean esittely.

gdb:n skriptaaminen

Komentorivikäyttöistä debuggeria voi luonnollisesti skriptata oman, jäykähkön, syntaksinsa mukaisesti. Tämän demon Makefile automatisoi ohjelman jäljen kirjaamisen lokiin seuraavalla komennolla (voi kokeilla erillisenä):

gdb -batch -x gdbkomennot_malli malliharkka

Tässä gdb käynnistyy argumentilla -batch pyydetysti "eräajona" eli se ei odota interaktiivisia syötteitä. Sen sijaan se suorittaa (-x == "execute"(?)) tiedostossa gdbkomennot_malli olevat komennot. Voit tutkia kyseistä tiedostoa ja todeta, miten se tuottaa demossa tutkittavan jäljen. Kaikki komennot ovat käyttökelpoisia myös interaktiivisessa käytössä, mukana on vanhoja tuttuja kuten stepi ym.

Alustavia huomioita virtuaalimuistista

Debuggerin kanssa ollaan sillä äärilaidalla, johon sovellusohjelmoija syvimmillään pääsee tietokonetta käyttämään. Ohjelma on käännetty tietylle prosessorille ja tietylle käyttöjärjestelmälle.

Tutkitaan tarkoin sellaisen käskyn suorittamista, joka näkyy debuggerissa seuraavanlaisena:

0x400606 <main+15>:     movq   $0xffffffffffffffff,-0x40(%rbp)

Periaatteessa on täysin mahdollista, että ennen tätä käskyä tulisi kellokeskeytys ja prosessi joutuisi ready-jonoon odottelemaan seuraavaa vuoroaan. Nythän se on joka tapauksessa pysäytettynä debuggerin toimesta. Pelit on seis, mutta se ei ohjelman kannalta vaikuta: Ohjelma itse ei tiedä, onko se keskeytettynä vai ei.

Seuraavassa hetkessä prosessori noutaisi käskyn. Se olisi virtuaalimuistiosoitteesta 0x400606, jonka prosessori muuntaisi fyysiseksi osoitteeksi käyttäen 48-bittisen virtuaaliosoitteen osia osoitteenmuodostuksessa:

+----------------------------------+-----------+-----------------+
|Hierarkkinen indeksointi          | Sivun     | Muistipaikan    |
|sivutaulun hakemiseen             | indeksi   | indeksi sivulla |
|                                  | taulussa  |                 |
|                                  |           |                 |
|000000000   000000000   000000010 | 000000000 | 011000000110    |
|                                  |           |                 |
+----------------------------------+-----------+-----------------+
|       Korvautuu osoitteenmuodostuksessa      | pysyy samana    |
|          sivutaulun tietojen mukaan          |                 |
+----------------------------------------------+-----------------+

Käyttöjärjestelmän muistinhallintaosio ylläpitää sivutauluja ja niiden hakemiseen liittyviä tietorakenteita. Prosessin käynnistyksen yhteydessä se on luonut tälle prosessille yksilöllisen sivutaulun. Osoitteenmuunnos tapahtuu laitteistossa prosessoriin, väyliin ja välimuisteihin liitetyn muistinhallintayksikön (memory management unit) eli MMU:n toimesta joka kerta kun jotakin osoitetta käytetään.

Käsky, jonka binäärikoodi tuosta kohtaa muistia löytyy, on siis seuraavanlainen:

movq   $0xffffffffffffffff,-0x40(%rbp)

Tämän käskyn suoritus tulee siirtämään lukuarvon -1 (kaikki bitit ykkösiä, heksaesitys 0xffffffffffffffff) virtuaalimuistiosoitteeseen, joka saadaan vähentämällä RBP:n arvosta 64 (lisätään etumerkillinen heksaluku -0x40). Kyseinen muistiosoite, ja siis siirron kohde, tulee olemaan:

RBP-rekisterin arvo
|
|              plus
|              |
|              | Käskyn binäärikoodiin sisällytetty vakiosiirros
|              | |
|              | |                     64-bittiseen rekisteriin
|              | |                     jää tässä ynnäyksessä
|              | |                     tulokseksi tämä luku
|              | |                     |
0x7fffffffe120 + -0x40              == 0x7fffffffe0e0

Eli bitteinä:

+----------------------------------+-----------+-----------------+
|Hierarkkinen indeksointi          | Sivun     | Muistipaikan    |
|sivutaulun hakemiseen             | indeksi   | indeksi sivulla |
|                                  | taulussa  |                 |
|                                  |           |                 |
|011111111   111111111   111111111 | 111111110 | 000011100000    |
|                                  |           |                 |
+----------------------------------+-----------+-----------------+
|       Korvautuu osoitteenmuodostuksessa      | pysyy samana    |
+----------------------------------------------+-----------------+

Käskyn suorituksessa:

  • prosessori tekee kohdeoperandin osoitteenmuunnoksen fyysiseksi osoitteeksi
  • väylä siirtää luvun keskusmuistiin (varsinainen toimenpide).
  • RIP:n arvo päivittyy seuraavan käskyn osoitteksi. Tässä tapauksessa lukuarvoksi 0x40060e.

Tai siltä ainakin näyttää. (Varsinaisesti pelissä on L1- ja L2 -välimuistit, muistinhallintayksikkö MMU ja sen TLB-puskurit; seuraava käskykin voi olla jo pitkään ollut suorituksessa tai suoritettuna johtuen liukuhihnoista ja ennakoivasta suorituksesta. Tai sitten suoritus on tehty emulaattorilla, simulaattorilla, virtuaalikoneella tai ainoastaan ohjelmaansa debuggaavan kehittäjän tai harjoitustyötä tekevän opiskelijan pään sisäisessä mielikuvamaailmassa. Millään näillä teknisillä suunnittelun ja optimoinnin urotöillä ei ole vaikutusta siihen, miten ohjelman suoritus näyttäytyy prosessoriarkkitehtuurirajapinnassa eli konekielikoodina.)

Pakollinen palautustehtävä

Demo palautetaan samalla tavalla kuin aiemmatkin.

Tästä demosta palautetaan tasan yksi tiedosto nimeltään "d05_vastaus.txt", johon on täydennetty itse kokeilemalla löydetyt vastaukset.

Toivottavasti työskentely jollain kunnollisella tekstieditorilla ja useilla pääteyhteysikkunoilla (screenissä tai muuten) on pikkuhiljaa muotoutumassa mukavammaksi ja mukavammaksi :).