ITKA203 Käyttöjärjestelmät -kurssin Demo 6 keväällä 2018. Tehdään itse pieni aliohjelma konekielellä.
Paavo Nieminen, paavo.j.nieminen@jyu.fi
STATUS: Tämä on nyt lopullinen vuodelle 2018. Alkuperäiseen on lisätty myös "juonipaljastuksia" -osio, jota voi katsoa, jos ei ratkea muuten.
DEADLINE: Tee, kun ehdit. (Kevään 2018 ensimmäisen kurssiarvostelun osalta dedis oli 28.5.2018, mutta parempi myöhään kuin ei milloinkaan...)
Contents
Päätavoite:
- Tietämyksesi tietokoneen toiminnasta ja konekielestä syvenee.
- Esimerkiksi syventävän kurssin Kääntäjätekniikka alku on pehmeämpi, kun olet tehnyt hieman konekieltä käsipelillä. Samoin syventävän kurssin Ohjelmistoturvallisuus laajempi tekninen versio on sitä helpompi mitä enemmän konekielen toiminta on ehtinyt hahmottua. Sama pätee muihinkin laiteläheiseen ohjelmointiin liittyviin kursseihin ja työtehtäviin tulevaisuudessa.
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 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.
Valmistele hakemisto tätä demoa varten ja hae pieni koodipaketti seuraavin komennoin:
wget https://yousource.it.jyu.fi/itka203-kurssimateriaalikehitys/itka203-kurssimateriaali-avoin/blobs/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 syötetiedostosta tulevat tavut ja palauttaa tieto, mikä tavu syötteessä esiintyi useiten.
Huomioita:
Strategia ongelman ratkaisemiseksi yleisellä tasolla:
Tehtävä siis aikalailla 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.
Perusvinkit:
Joitain 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 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. 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ää shellistä 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:
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 vähän hankalaa.. 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!
Lisää vinkkejä saattaa tulla, jos keksitään, mikä olisi hyödyllistä, mutta ei antaisi suoria vastauksia... Tässä on kyllä jo aika suoria vinkkejä annettu. Eli enempää vinkkejä ei välttämättä tule kuin korkeintaan "pitkin hampain"...
Tässä tapauksessa ohjelma toimisi (hieman "säkällä") vaikka käyttäisit 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ä lähestyy juonipaljastusta, mutta ei vielä ole aivan sellainen. Kerrataan pari edellä mainittua perusvinkkiä:
Huomattiin 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 kaarisulku '{'.
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 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 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, RBX, 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/kj18/demovedokset/spoilereita_d06.html
Keväällä 2018 kurssin demot ja niiden palautus hoidetaan osoitteessa itka203.it.jyu.fi olevan järjestelmän kautta. Kullekin demolle on oma palautuslaatikko, johon tehtävässä tuotettu tiedosto palautetaan.
Tästä demosta palautetaan tasan yksi tiedosto nimeltään "useimmiten.s" jossa on yllä selitetyn tehtävänannon mukainen, toimiva assembler-aliohjelma.