ITKA203 Käyttöjärjestelmät -kurssin Demo 6 keväällä 2018 ja 2019 ja 2020 ja 2021 ja 2022 ja 2023. Tehdään itse pieni aliohjelma konekielellä.
Paavo Nieminen, paavo.j.nieminen@jyu.fi
Aikataulutuksessa voit ottaa huomioon sen, että suoraan tähän demoon liittyviä kysymyksiä ei tule tenttiin. Tentin lähipäivät voi rauhoittaa kertaamiseen ja tenttivalmistautumiseen. Kurssin suorittamiseksi tämä on pakollinen, joten kannattaa tehdä kuitenkin rivakasti, että saa arvosanan ensimmäisen tentin perusteella pien opetusperiodin päätyttyä. Älä jätä roikkumaan vuosiksi, kun on näin pitkälle jo tultu!
Demo-ohjeisiin on kertynyt asteittain tarkentuvia vinkkejä, ja keväällä 2020 nauhoitettiin myös "kädestä pitäen" -ohjevideot. Eli huoli pois: ohjeita tämän demon tekemiseen on riittämiin! Voit kokeilla, mihin pisteeseen asti saat omatoimisesti, ja sitten käydä katsomaan seuraavan tarkkuustason opastuksia.
Kaikista viimeiseen ohjevideoon pitää pyytää tarvittaessa erikseen salainen linkki/polkuavain opettajalta - se ei ole julkinen, koska se tavallaan spoilaa koko demon pelkäksi mallin perässä tekemiseksi... Minimivaatimuksena sekin riittää. Arvomaailman kasvattamiseksi toivomme kuitenkin ahkeraa omatoimista yrittämistä, ja tässä on mahdollisuus arvioida oman osaamisen nykyistä tilaa: Kuinka paljon täytyy tukeutua ohjeisiin, ja kuinka paljon onnistuu omatoimisen tutkimisen kautta.
Tässä tehtäväohjeessa ei vielä ole yhtään juonipaljastusta. Otsikon "Juonipaljastuksia" alla on klikattava linkki, joten vahingossa ei kukaan joudu varsinaisia paljastuksia näkemään :).
Sisällys
Päätavoite:
- Tietämyksesi tietokoneen toiminnasta ja konekielestä syvenee.
- Saavutat työelämässä ja jatkokursseilla odotetun perustaitotason konekielen ymmärtämisessä. Esimerkiksi ohjelmointikielten toteutuksen ja suunnitteluperiaatteiden ymmärtäminen tulee mahdolliseksi, kun olet tehnyt hieman konekieltä käsipelillä. Samoin ohjelmistojen tietoturvallisuuden ("tekninen kyberturvallisuus") ymmärtäminen on sitä helpompaa mitä enemmän konekielenkin toiminta on ehtinyt hahmottua. Sama pätee muihinkin laiteläheiseen ohjelmointiin liittyviin kursseihin ja työtehtäviin tulevaisuudessa, mukaanlukien tietoliikenne, teollisuuden mikrokontrolleriohjelmointi ja IoT.
Edelleen käytetään nykyaikaisia työkaluja, joita kurssilla on tähän asti käytetty. Tehdään AMD64 -prosessorin (ts. "x86-64") konekieltä GNU:n AT&T-assemblersyntaksilla, jota on tähänkin asti nähty debuggerin tulosteissa. Ohjelma käännetään ja linkitetään komentoriviltä GNU:n työkaluilla Jyväskylän yliopiston suorakäyttökoneella (jalava tai halava), jossa sitä myös kokeillaan. Jotta työskentely olisi näppärää, screen-ohjelman, shellin ja tekstieditorin käyttö on hyvä olla hanskassa. Koko ajan voi opetella niitäkin lisää.
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/d06/d06_paketti.zip unzip d06_paketti.zip
Tutki paketista avautunutta runkoa aiemmin opituilla keinoilla (mm. komennot ls, less, tekstieditori). Mukana on Makefile, joka automatisoi vaiheita. Seuraava komento kääntää ohjelman mallirungon:
make
Paketissa on mukana konekielisen aliohjelman tynkä useimmiten.s, johon sinun tulee tehdä rajapinnan ja dokumentaation mukainen toiminnallisuus. Muista kääntää ja kokeilla aina pienten muutosten jälkeen, ennen kuin koodi menee hallitsemattomaan tilaan liian monen muutoksen kautta!
Aliohjelmallesi useimmiten() tulee ensimmäisenä parametrina tiedosto-osoitin ja toisena parametrina kokonaisluku, jonka C-kirjaston kutsu fgetc() palauttaa luettavan tiedoston loputtua. Aliohjelmasi tulee lukea C-alustakirjaston fgetc() -kutsua käyttäen kaikki standardisyöttövirrasta tulevat tavut ja palauttaa tieto, mikä tavu syötteessä esiintyi useiten.
Yksinkertainen tehtävä, onko? Jälkikäteen ajatellen tulee olemaan, mutta tehtävä on kuitenkin monivaiheinen, eikä ratkaisu tule ilman järjestelmällistä suunnittelua.
Huomioita:
Strategia ongelman ratkaisemiseksi yleisellä tasolla:
Tehtävä siis jotakuinkin "vaativaa Ohjelmointi 1 -tasoa". Nyt vaan tehdään se konekielellä.
Rajoituksia ja vapauksia:
Tehtävässä on yhdistettävä useita tiedonmurusia luentomonisteen alkupuolelta (noin sivut 1-84). Aiemmissa demoissa hankitut taidot komentorivistä, debuggerista ym. auttavat, ja niitä on tarkoitus harjoitella samalla lisää.
Perusvinkit:
Joitain tekemistä helpottavia yksityiskohtia:
Ohjelma lukee syötteen standardisyöttövirrasta. Komentoriviltä kokeillessa voit antaa merkit putkittamalla samoin kuin esimerkkinä annetussa Makefilessä tehdään:
echo "aabbbba" | ./demo06
Voit myös ohjata syötteeksi tiedoston kuorioperaattorilla < seuraavasti:
./demo06 < joku_testitiedosto
Voit myös näppäillä pienen testijonon suoraan päätteeltä. Huomaa silloin seuraavaa: Syöte alkaa mennä ohjelmalle vasta, kun painat rivinvaihtoa ja silloin mukaan tulee aina myös rivinvaihtomerkki eli Linuxissa tavu 0x0a. Syötteessä voi olla monta riviä. Saat lopetettua syötteen näppäilemällä Ctrl-d, josta ei tule enää mitään merkkiä, vaan tämän näppäilyn jälkeen fgetc() palauttaa EOF.
Debuggeri on mittaamattoman arvokas työkalu tässäkin hommassa. Voit käynnistää kuoresta näin:
gdb demo06
Gdb:ssä voit laittaa breakpointteja vaikkapa symbolisiin osoitteisiisi:
break useimmiten
tai:
break lue_seuraava_merkki
tai mitä symboleita nyt oletkaan käyttänyt ohjelmassasi!
Huomaa edelleen, että debuggerissakin ohjelma lukee standardisyöttövirtaa (ks. edellinen vinkki). Debuggerissa voit ohjata ohjelmalle syötetiedoston käynnistämällä sen näin:
run < tiedostonimi
Voit tehdä omia "helppoja" testitiedostoja, niin voit askeltaa vaikka koko algoritmin läpi ja varmistua muistin sisällöstä kussakin vaiheessa.
Vaihtoehtoisesti voit syöttää merkkejä näppäimistöltä tyyliin "abbacd" ja lopettaa syötteen näppäilemällä Ctrl-d. Debuggerissa tätä ei kokeilujeni perusteella ilmeisesti voi tehdä ennen kuin on näppäilty syötteeseen ensimmäinen rivinvaihto.
Tässäkin tyyli on vapaa, mutta toiset tavat on näppärämpiä kuin toiset. Valitse itselle sopiva.
Esim. tällainen tuloste voisi olla hyödyllinen, jos käyttäisit 64-bittisiä lukuja tavuesiintymien laskemisessa:
x /256g $rsp
Tuohan näyttäisi 256 "giant" eli 64-bittistä lukua alkaen pinon huippuosoitteesta. Havaittiin tämä hyödylliseksi ainakin mikroluokassa Open labrapäivässä 14.5.2018 (ja 21.5.2018 ja 28.5.2018)
Merkin lukeminen tiedostosta tapahtuu kutsumalla C-aliohjelmaa fgetc(). Miten siis assemblerilla? Ihan vaan call-käskyllä seuraavasti:
call fgetc # Linkkeri osaa laittaa osoitteeksi C:n fgetc():n alun.
Ennen kutsua on laitettava parametrit ABIn mukaisesti. Paluuarvo on ABIn määräämässä paikassa. Kaikki tämä näkyy myös demon 5 esimerkkialiohjelmassa.
fgetc():n dokumentaatio esim. http://pubs.opengroup.org/onlinepubs/009695299/functions/fgetc.html - tiedoston loppumisen tunnistaa siitä, että palautuu EOF. Tämä on joku kokonaisluku, mutta meidän ei tartte nyt välittää sen varsinaisesta arvosta (joka sattuu olemaan GNU:n C-kirjastossa -1), koska C-kielinen pääohjelma antaa meidän aliohjelmalle toisena parametrina tämän luvun. Meidän lukusilmukka pitää siis lopettaa siinä vaiheessa, kun fgetc():n paluuarvona on sama kokonaisluku kuin meille annettu toinen parametri.
Virallinen ABI löytyy esim. http://refspecs.linuxbase.org/elf/x86_64-SysV-psABI.pdf mutta luentomonisteessa on kiteytetty tähän tarpeeseen olennaisimmat kohdat poislukien seuraava:
- ABI lupaa, että rekisterit RBX, R12, R13, R14 ja R15 eivät muutu aliohjelmakutsussa. Näitä voi siis käyttää paikallisina muuttujina. Muista dokumentoida, mitä aiot käyttää mihinkin tarkoitukseen.
- Myöskään oma aliohjelmasi ei saa jättää mainittuja rekistereitä lopussa eri arvoon kuin missä ne aliohjelmaan tultaessa olivat. Kutsuja on voinut pitää niissä jotain tarpeellista dataansa. Voit siis esimerkiksi laittaa ne alussa pinoon talteen ja palauttaa lopussa. Pysy kartalla pinokehyksesi rakenteesta!
Vertailukäskyn operandien järjestys on ainakin itselleni aina vaikea muistaa, ja pittää joka kerta kokeilla debuggerilla tai kaivaa netistä ohjeet. Tässä nyt esimerkki valmiina:
cmp %rax, %rbx # Vertaa rekisterien %rax ja %rbx arvoja jg osoite # Hyppää, jos pätee %rbx > %rax
Eli GNU-assemblerissa niin, että "jos jälkimmäinen on ehdon mukaisessa suhteessa ensimmäiseen, niin hyppy tapahtuu". Lisätietoa esim. https://en.wikibooks.org/wiki/X86_Assembly/Control_Flow
Miten viitataan indeksin mukaiseen alkioon? Yksi mahdollinen peruskaava olisi optimoimattoman C-käännöksen ehdotus:
lea 16(%rsp), %rsi # Taulukon alkuosoite olis vaikka RSP+16
# (omassa koodissasi riippuu tekemistäsi
# ratkaisuista tietysti)
mov %rcx,%rdx # Olisit vaikka päättänyt käyttä RCX:ää
# indeksinä (riippuu taas ratkaisuistasi)
shl $3,%rdx # Rakentaisit siirroksen 64-bittisten lukujen
# taulukkoon kertomalla indeksin 8:lla eli
# siirtämällä bittejä 3 pykälää vasemmalle
addq %rdx,%rsi # Lisäisit siirroksen alkuosoitteeseen
cmpq $0,(%rsi) # Tekisit, mitä tarvitsee, alkiolle joka on
# indeksin mukaisessa osoitteessa.
Mutta tämä on turhan hankalaa.. AMD64-prosessorissa on olemassa suorempikin tapa:
addq $1, -2064(%rbp, %rax, 8) # Kajoaa muistiosoitteeseen, joka löytyy
# RAXin mukaisesta indeksistä 8 tavun
# mittaisiin alkioihin, joista ensimmäinen
# on osoitteessa RBP-2064.
#
# Varsin käyttökelpoinen esimerkiksi tässä
# tavumäärien laskemisessa!!
Huomaa, että samaa kaavaa voi käyttää muihinkin käskyihin kuin ykkösen lisäämiseen. Toinen esimerkki:
movq $0, -2048(%rbp, %rax, 8) # Sijoittaa 64-bittisen nollan
# alkaen osoitteesta
# RBP-2048+8*RAX
#
# Käyttökelpoinen taulukon nollaamisessa.
Syntaksista lisää esim. https://en.wikibooks.org/wiki/X86_Assembly/GAS_Syntax
Myös Google on ystävä näitä(kin) juttuja tehdessä. Kunhan pysähdyt miettimään, mitä kaikki tarkoittaa. Tarvitaan aina hallittu "copy-paste-modify". Suora copy-pastaus ilman ajatuksella tehtyä modify-vaihetta on tuhon tie!
Tässä tapauksessa ohjelma toimisi (täysin säkällä) vaikka käyttäisit aivan kaikkeen kurssilla tähän asti nähtyjä 64-bittisiä kokonaislukuja. Jos tekee mieli olla vähemmän tuurin varassa, voit huomioida seuravaa:
Kuten sanottu, tässä tapauksessa ja tällä kurssilla on lupa luottaa "tuuriinkin".
Tämä ei vielä ole juonipaljastus, vaikka vähän sellaista lähestyykin. Kerrataan pari edellä mainittua perusvinkkiä:
Huomattiin jo kevään 2018 aikana, että tehtävässä voi olla hankala keksiä, mistä lähdetään liikkeelle. Tässä on yksi suositeltu toimintakaava tähän tilanteeseen. Käytännössä tämä on vain yleinen ongelmanratkaisun kaanon sovellettuna tähän demoon:
Varmista, että pystyt kajoamaan koodiin työkaluillasi. Tee kokeeksi sellainen muutos, että aliohjelmasi palauttaa nollan sijasta vaikkapa luvun 123. Käännä ja suorita ohjelma varmistuen, että se tulostaa vastauksen olevan merkki 123, joka ASCIIn mukaisesti tulostettuna olisi avaava aaltosulku '{'.
Hae tilanteesta positiivinen fiilis: Olet tehnyt konekieliseen koodiin hallitun muutoksen. Kaikki on näpeissäsi. Koodi toimii, ja ymmärrät sen tämänhetkisen toiminnan täysin. Mielellään ei tule missään vaiheessa vastaan syytä poiketa tästä tilanteesta.
Havaitse, että ainakin pinokehyksen luominen ja vapauttaminen täytyy joka tapauksessa tapahtua. Samalla tavoin kuin demo 5:ssä nähtiin. Koodaa siis tarvittavat rivit aliohjelman alkuun ja loppuun. Käännä ja aja, kommentoi. Varmemmaksi vakuudeksi askella debuggerissa ja katso, että kehys syntyy ja tuhoutuu siten kuin demo 5:ssä nähtiin valmiiksi tehdyn esimerkin kanssa.
Tee ratkaisu oman pinokehyksen sisällöstä: Mihin kohtaan tulee taulukko, mihin kohtaan muu tarvittava. Suosituksena voisi olla, että varaat 8 tavua tilaa molemmille parametreille ja 256:lle kokonaisluvulle laskentaa varten. Muokkaa aliohjelman alkua vastaavasti ja dokumentoi valittu rakenne, eli missä kohtaa kehystä pidät mitäkin. Käännä ja aja. Askella debuggerissa, jos et muuten usko, että varaus on OK.
Laita koodi, joka tallentaa parametrit valitsemiisi paikkoihin. Käännä. Debuggaa tarvittaessa nähdäksesi, että parametrit menee varmasti talteen.
Havaitse, että aliohjelman alku ja loppu on kunnossa. Toiminnallisuus tulee seuraavaksi niiden väliin. Laita ennakoiva kommentti, mitä osioita luultavasti tulee.
Tee koodi, joka nollaa taulukon. Käännä. Varmistu debuggerilla (ks. vinkki yllä), että taulukossa on varmasti 256 kappaletta nollaa.
Tee koodi, joka kutsuu fgetc():tä, kunnes se palauttaa EOF. Älä vielä edes mieti muuta toiminnallisuutta. Pieni askel kerrallaan! Käännä, aja, debuggaa. Totea, että ohjelma jää odottamaan syötettä ja että silmukka pysähtyy tiedoston päättymisen kohdalla. Helposti voi tulla aluksi kaatuminen tai ikuinen silmukka. Syy on mahdollista selvittää, kun nyt työn alla on vain muutama käsky. Varmista, että fgetc():n parametrit ja paluuarvo menevät oikein. Muista, että fgetc()-kutsu saa sotkea suuren osan rekistereistä, mm. RAX, RCX, RDX, RDI, RSI... Olet jo varautunut tämän hoitamiseen edellisissä askeleissa. Jumppaa näitä muutamaa riviä, kunnes ohjelma näyttää varmuudella lukevan syötteestä kaikki merkit ja lopettavan lukemisen EOFiin.
Hae onnistumisen fiilis siitä, että olet homman puolivälissä ja ymmärrät koodisi täysin.
Lisää koodi, joka summaa merkin saapuessa ykkösen taulukkoon oikeaan kohtaan. Testaa debuggerissa helpolla syötteellä. Esim. aseta breakpoint lukusilmukkasi perään. Käynnistä. Näppäile "abbccc", rivinvaihto ja Ctrl-D. Oletettu tilanne pysähdyspisteessä on, että taulukossa on peräkkäiset luvut 1, 2 ja 3, koska merkit 'a', 'b', 'c' ovat ASCIIssa peräkkäin. Lisäksi pitäisi olla ykkönen rivinvaihtomerkin kohdalla (indeksi 10).
Vasta sitten, kun lukusilmukka on testattu, on toiveita saada seuraavat vaiheet maaliin. Varmistu siis vielä, että edellinen kohta on OK.
Lisää koodi, joka etsii taulukon suurimman alkion. Tämä on tulossa lukemisen jälkeen, joten enää ei tulla kutsumaan fgetc():tä tai muutakaan ulkopuolista aliohjelmaa, joten voit käyttää apumuuttujina rekistereitä RAX, RCX, RDX, RDI, RSI,... Esimerkiksi:
- Tee valinta, mitä apumuuttujia tarvitset, ja dokumentoi kommenttiin.
- Sitten silmukkarakenne eli taulukon läpikäynti toistaiseksi ilman toiminnallisuutta; varmista, ettei tullut syntaksivirheitä tai ikuista silmukkaa. Älä yritä liikaa kerralla.
- Lopulta silmukan sisään logiikka, jolla löytyy isoimman alkion indeksi.
- Jumppaa, kunnes toimii.
Varmista, että aliohjelmasi sijoittaa paluuarvon ABIn mukaisesti RAX-rekisteriin ennen paluuta kutsuvaan ohjelmaan. Viimeistään tässä vaiheessa luovut esimerkkirungossa olleesta käskystä, joka sijoitti paluuarvoksi "vain jotakin".
Testaa muutamalla erilaisella syötteellä.
Iloitse - olet nyt astunut assembler-koodaajien kerhoon! Muista myös palauttaa demo ja näyttää teoriaosaaminen tentissä, niin saat kurssista opintopisteet...
Jos ei nämä vinkit vielä auttaneet, voit hätäpainikkeena klikata seuraavaa linkkiä, jossa on vielä superlisävinkkejä: http://users.jyu.fi/~nieminen/kj23/demovedokset/spoilereita_d06.html
Demo palautetaan samalla tavalla kuin aiemmatkin.
Tästä demosta palautetaan tasan yksi tiedosto nimeltään "useimmiten.s" jossa on yllä selitetyn tehtävänannon mukainen, toimiva assembler-aliohjelma.