11. Pino ja aliohjelma

Tässä luvussa syvennymme tarkemmin pinon käyttämiseen aliohjelman toteutuksessa konekielisessä ohjelmoinnissa. Pinon avulla voidaan toteuttaa aliohjelman kutsuminen ja muistinvaraukset niin, että aliohjelmat pystyvät kutsumaan toisiaan eri tavoilla.

Tarkemmin ottaen tutustumme aliohjelmien toteuttamiseen 64-bittisessä Linux-ympäristössä. Tähän liittyy tiettyjä käytäntöjä, joita seuraamalla omia konekielisiä aliohjelmia voidaan kutsua myös muualta, kuten C-ohjelmasta.

Pinon toiminta

Pino (stack) on muistialue, jota käytetään aliohjelmakutsujen toteuttamiseen sekä aliohjelmien paikalliseen muistinvaraukseen. Ohjelman käynnistyessä käyttöjärjestelmä varaa ohjelmalle muistialueen, jota se voi käyttää pinona.

Konekieli tarjoaa tukea pinon käyttämiseen rekisterien ja komentojen kautta. Rekisteri rsp on pinorekisteri (stack pointer), joka osoittaa pinon päälle. Komennot push ja pop lisäävät ja poistavat pinossa olevaa tietoa.

Pino kasvaa muistissa oikealta vasemmalle: rekisteri rsp liikkuu vasemmalle, kun pinoon lisätään tietoa, ja oikealle, kun pinosta poistetaan tietoa. Esimerkiksi seuraava kuva esittää muistissa olevaa pinoa, johon on lisätty 64-bittiset luvut 1, 2 ja 3. Tässä rekisteri rsp osoittaa pinon päälle luvun 3 muistiosoitteeseen.

Pinokomennot

Komento push lisää arvon pinon päälle ja komento pop hakee ja poistaa arvon pinon päältä. Komentoja voidaan käyttää esimerkiksi seuraavasti:

    mov rax, 1
    mov rbx, 2

    push rax
    push rbx
    pop rax
    pop rbx

Tämä koodi vaihtaa keskenään rekisterien rax ja rbx arvot:

1. push rax lisää pinon päälle rekisterin rax arvon.
2. push rbx lisää pinon päälle rekisterin rbx arvon.
3. pop rax hakee pinon päältä arvon rekisteriin rax.
4. pop rbx hakee pinon päältä arvon rekisteriin rbx.

Pinon vaiheet koodin suorituksen aikana:

    xor rax, rbx
    xor rbx, rax
    xor rax, rbx

Pinorekisteri

Pinoa voidaan käsitellä myös suoraan pinorekisterin rsp kautta. Pinosta voidaan varata ja vapauttaa tilaa vähentämällä (sub) ja kasvattamalla (add) rekisterin arvoa. Komennolla mov voi kopioida tietoa esimerkiksi pinon ja rekisterien välillä.

Esimerkiksi seuraava koodi varaa pinosta 16 tavua tilaa, kopioi rekisterien rax ja rbx arvot varatulle alueelle ja vapauttaa sitten varatun muistin.

    mov rax, 1
    mov rbx, 2

    sub rsp, 16
    mov [rsp], rax
    mov [rsp+8], rbx
    add rsp, 16

Pinon vaiheet koodin suorituksen aikana:

Komennot push ja pop voidaan myös korvata pinorekisterin käsittelyllä. Esimerkiksi seuraava koodi vastaa komentoa push rax:

    sub rsp, 8
    mov [rsp], rax

Seuraava koodi puolestaan vastaa komentoa pop rax:

    mov rax, [rsp]
    add rsp, 8

Aliohjelman toteutus

Aliohjelman toteutus komennoilla call ja ret perustuu pinon käyttämiseen. Komento call lisää ensin pinoon kutsukohdan paluuosoitteen ja siirtää sitten koodin suorituksen aliohjelman alkuun. Komento ret puolestaan hakee paluuosoitteen pinosta ja siirtää koodin suorituksen sinne.

Kutsukohdan paluuosoite tarkoittaa käytännössä sen komennon osoitetta, joka on koodissa komennon call jälkeen. Komento call muuttaa rekisteriä rip niin, että suoritus siirtyy aliohjelmaan, ja vastaavasti komento ret muuttaa rekisteriä rip niin, että suoritus siirtyy komentoa call seuraavaan komentoon.

Tarkastellaan esimerkkinä seuraavaa ohjelmaa:

swap_regs:
    push rax
    push rbx
    pop rax
    pop rbx
    ret

_start:
    mov rax, 1
    mov rbx, 2
    call swap_regs
    add rax, rbx

Tässä komento call swap_regs lisää pinoon komennon add rax, rbx muistiosoitteen ja siirtää koodin suorituksen kohtaan swap_regs. Komento ret puolestaan hakee pinosta muistiosoitteen ja siirtää koodin suorituksen sinne.

Pinon vaiheet koodin suorituksen aikana:

Tässä next_rip tarkoittaa kutsukohdan paluuosoitetta eli rekisterin rip arvoa aliohjelman suorituksen jälkeen.

Aliohjelman käytännöt

Komentojen call ja ret avulla aliohjelman tiedonvälityksen voisi toteuttaa useilla tavoilla, mutta käyttöjärjestelmissä on tiettyjä käytäntöjä tähän liittyen. Tällaisia käytäntöjä ovat esimerkiksi, miten parametrit välitetään aliohjelmalle ja miten aliohjelma välittää paluuarvon kutsuvalle koodille.

64-bittisessä Linux-ohjelmoinnissa aliohjelmien toteutuksen käytäntönä on System V ABI -malli, johon tutustumme seuraavaksi. Tämän mallin seuraaminen omissa aliohjelmissa on hyödyllistä, koska silloin aliohjelmia pystyy kutsumaan odotetulla tavalla myös oman koodin ulkopuolelta.

Parametrit ja paluuarvo

Aliohjelman kuusi ensimmäistä parametria välitetään rekistereissä rdi, rsi, rdx, rcx, r8 ja r9 tässä järjestyksessä. Jos aliohjelmalla on yli kuusi parametria, loput parametrit välitetään pinon kautta käänteisessä järjestyksessä.

Esimerkiksi jos aliohjelmalla on kaksi parametria, ensimmäinen parametri välitetään rekisterissä rdi ja toinen parametri välitetään rekisterissä rsi.

Jos aliohjelmalla on paluuarvo, se välitetään kutsuvalle koodille rekisterissä rax.

Tarkastellaan esimerkkinä seuraavaa C-kielistä koodia, joka laskee lukuvälin lukujen summan kutsumalla funktiota calc_sum:

long calc_sum(int a, int b) {
    long sum = 0;
    for (int i = a; i <= b; i++) {
        sum += i;
    }
    return sum;
}

int main(void) {
    long sum = calc_sum(1, 100);
}

Tässä on suunnilleen vastaava konekielinen koodi:

calc_sum:
    mov rax, 0
calc_loop:
    cmp rdi, rsi
    jg calc_end
    add rax, rdi
    inc rdi
    jmp calc_loop
calc_end:
    ret

_start:
    mov rdi, 1
    mov rsi, 100
    call calc_sum

Tämä aliohjelma toimii seuraavasti:

• Ensimmäinen parametri välitetään rekisterissä rdi ja toinen parametri välitetään rekisterissä rsi.
• Aliohjelma laskee lukuvälin summan rekisteriin rax, josta tulee aliohjelman paluuarvo. Aluksi rax saa arvon 0.
• Silmukan alussa koodi tarkastaa, onko rdi:n arvo suurempi kuin rsi:n arvo. Jos on, silmukka päättyy.
• Muuten rdi:n arvo lisätään rax:n arvoon, rdi:n arvo kasvaa yhdellä ja koodi hyppää takaisin silmukan alkuun.

Rekisterien säilytys

Rekisterit rbx, rsp, rbp, r12, r13, r14 ja r15 ovat säilytettäviä, mikä tarkoittaa, ettei aliohjelma saa muuttaa pysyvästi näiden rekisterien sisältöä. Ideana on, että aliohjelmaa kutsuva koodi voi luottaa siihen, että näiden rekistereiden sisältö on aliohjelman kutsumisen jälkeen sama kuin ennen aliohjelman kutsumista.

Aliohjelma saa kuitenkin muuttaa vapaasti muita rekistereitä. Esimerkiksi äskeisessä aliohjelmassa calc_sum rekisterin rdi sisältö muuttuu aliohjelmassa, koska rekisteriä käytetään silmukan toteuttamiseen. Tämä ei ole ongelma, koska rdi ei ole säilytettävä rekisteri.

Jos aliohjelma muuttaa säilytettävää rekisteriä suorituksensa aikana, sen tulee palauttaa rekisterin sisältö ennalleen ennen aliohjelman päättymistä eli komennon ret suorittamista. Yleinen tapa toteuttaa tämä on kopioida rekisterin sisältö alussa pinoon ja palauttaa se pinosta lopuksi.

Esimerkiksi seuraava aliohjelma muuttaa sisäisesti rekisterin rbx sisältöä mutta säilyttää sen kutsuvan koodin kannalta oikealla tavalla, koska aliohjelma lisää aluksi rekisterin arvon pinoon ja hakee lopuksi rekisterin alkuperäisen arvon pinosta.

modify_test:
    push rbx
    mov rbx, 42
    pop rbx
    ret

Pinokehys ja muuttujat

Aliohjelman pinokehys (stack frame) muodostuu pinossa säilytettävästä tiedosta, joka liittyy aliohjelman suoritukseen. Pinokehys sisältää ainakin aliohjelman kutsukohdan paluuosoitteen, ja se voi sisältää lisäksi esimerkiksi rekisterien arvojen kopioita sekä paikallisten muuttujien sisältöä.

Yleinen käytäntö on tallentaa rekisteriin rbp (base pointer) rekisterin rsp sisältö aliohjelman alussa. Tällöin aliohjelma pystyy viittaamaan pinossa oleviin paikallisiin muuttujiin kätevästi rekisterin rbp kautta. Koska rekisteri rbp on säilytettävä rekisteri, tähän liittyen yleinen käytäntö on lisätä aliohjelman alussa pinoon kopio rekisterin rbp sisällöstä ja palauttaa se aliohjelman lopussa.

Tarkastellaan esimerkkinä C-kielistä funktiota, joka suorittaa laskutoimituksen:

long calc_value(void) {
    long a = 123456789;
    long b = 987654321;
    return a * b;
}

Seuraavassa on vastaava konekielinen aliohjelma, joka käyttää rekisteriä rbp ja varaa pinosta tilaa muuttujille a ja b:

calc_value:
    push rbp
    mov rbp, rsp
    sub rsp, 16

    mov qword [rbp-16], 123456789
    mov qword [rbp-8], 987654321

    mov rax, [rbp-16]
    mov rcx, [rbp-8]
    imul rax, rcx

    add rsp, 16
    pop rbp
    ret

Aluksi koodi kopioi rekisterin rbp arvon pinoon, siirtää rekisteriin rbp rekisterin rsp arvon sekä varaa pinosta muistia 16 tavua muuttujille.

Koodi muodostaa muuttujien osoitteet suhteessa rekisterin rbp arvoon: muuttuja a on pinossa kohdassa rbp-16 ja muuttuja b on pinossa kohdassa rbp-8. Näiden osoitteiden avulla koodi tallentaa tietoa pinoon ja hakee tietoa pinosta.

Lopuksi koodi vapauttaa muuttujille varatut 16 tavua pinosta ja palauttaa rekisterin rbp sisällön alkuperäiseksi.

Huomaa, että edellisessä koodissa ja usein muutenkaan pinomuistin varaaminen muuttujille ei ole mitenkään pakollista, vaan samalla tavalla toimivan koodin voisi toteuttaa myös käyttämällä pelkkiä rekistereitä esimerkiksi seuraavasti:

calc_value:
    mov rax, 123456789
    mov rcx, 987654321
    imul rax, rcx
    ret

Kuitenkin pinomuistista on todellista hyötyä silloin, kun kaikkea aliohjelman käsittelemää tietoa ei voi säilyttää rekistereissä tai johonkin tietoon täytyy pystyä viittaamaan muistiosoitteen kautta (esimerkiksi systeemikutsun yhteydessä), jolloin se ei voi olla rekisterissä.

Pinon tasaaminen

System V ABI -mallissa aliohjelman kutsuessa toista aliohjelmaa pinon tulee olla tasattu niin, että pinorekisteri rsp osoittaa muistissa 16 tavun rajaan eli rekisterissä rsp olevan muistiosoitteen tulee olla jaollinen 16:lla. Tämän takia aliohjelman tulee lisätä pinoon sopiva määrä tavuja ennen toisen aliohjelman kutsumista.

Aliohjelman kutsuminen komennolla call aiheuttaa, että komento lisää pinoon 8-tavuisen kutsukohdan paluuosoitteen. Tämän takia pino ei ole tasattu aliohjelman suorituksen alkaessa. Kuitenkin jos aliohjelma lisää aluksi pinoon kopion 8-tavuisen rekisterin rbp sisällöstä, pino on jälleen tasattu.

Esimerkiksi seuraava koodi aliohjelman alussa tasaa myös pinon:

    push rbp
    mov rbp, rsp
    sub rsp, 16

Tässä komento push lisää ensin pinoon 8 tavua tietoa, minkä jälkeen koodi varaa pinosta 16 tavua tilaa. Tämän koodin jälkeen rekisteri rsp osoittaa 16 tavun rajaan ja koodi voi kutsua turvallisesti toista aliohjelmaa.

Jos aliohjelma ei kutsu mitään aliohjelmaa tai kutsuttava aliohjelma ei oleta tasattua pinoa, aliohjelman ei tarvitse välittää pinon tasaamisesta.

Esimerkkejä

Taulukon käsittely

Seuraava C-funktio laskee, montako kertaa luku esiintyy taulukossa:

int count(int *array, int n, int value) {
    int result = 0;
    for (int i = 0; i < n; i++) {
        if (array[i] == value) result++;
    }
    return result;
}

Tässä on vastaavalla tavalla toimiva konekielinen aliohjelma:

count:
    mov rax, 0
    mov rcx, 0
loop_start:
    cmp rcx, rsi
    je loop_end
    cmp [rdi+4*rcx], edx
    jne loop_skip
    inc rax
loop_skip:
    inc rcx
    jmp loop_start
loop_end:
    ret

Tässä tapauksessa parametreja on kolme, jolloin ne välitetään rekistereissä seuraavasti:

• rdi: osoitin taulukkoon (array)
• rsi: taulukon alkioiden määrä (n)
• rdx: haluttu taulukon alkio (value)

Konekielinen koodi laskee tuloksen rekisteriin rax ja käyttää rekisteriä rcx silmukan toteuttamisessa. Silmukka käy läpi taulukon alkiot ja tarkastaa jokaisen alkion kohdalla, onko se haluttu alkio.

Koska taulukko on int-tyyppinen, jokainen alkio vie tilaa neljä tavua. Tämän takia alkion sijainti muistissa saadaan laskettua kaavalla rdi+4*rcx, missä rdi on taulukon alkuosoite ja rcx on alkion indeksi.

Rekursiivinen aliohjelma

Tehdään seuraavaksi rekursiivinen konekielinen aliohjelma, joka laskee halutun Fibonaccin luvun seuraavan C-funktion tyylisesti:

long fibo(int n) {
    if (n <= 1) return n;
    return fibo(n - 1) + fibo(n - 2);
}

Ensimmäiset Fibonaccin luvut ovat:

Voimme toteuttaa aliohjelman seuraavasti:

fibo:
    cmp rdi, 1               ; n <= 1?
    jg fibo_calc
    mov rax, rdi             ; just return n
    ret
fibo_calc:
    push rbx
    push rdi
    dec rdi
    call fibo                ; calculate fibo(n - 1)
    mov rbx, rax             ; store result to rbx
    pop rdi
    sub rdi, 2
    call fibo                ; calculate fibo(n - 2)
    add rax, rbx             ; sum recursive results
    pop rbx
    ret

Koodi tarkastaa alussa, onko rekisterissä rdi annettu parametri enintään 1. Jos on, kyseessä on pohjatapaus, jossa riittää palauttaa suoraan annettu parametri rekisterissä rax. Jos ei ole, koodin tulee laskea tulos rekursiivisesti.

Koodin rekursiivinen osuus alkaa nimiöstä fibo_calc. Koodi kopioi ensin pinoon talteen rekisterit rbx ja rdi. Rekisteriä rbx käytetään apuna tuloksen laskemisessa, ja rekisteri rdi sisältää aliohjelman parametrin.

Koodi kutsuu ensin itseään rekursiivisesti, niin että rdi:n arvoa on vähennetty yhdellä. Tämä vastaa C-koodin kutsua fibo(n - 1). Kutsun tulos tulee rekisteriin rax, josta koodi kopioi sen rekisteriin rbx.

Tämän jälkeen koodi palauttaa pinosta rekisterin rdi alkuperäisen arvon ja vähentää sitä kahdella. Tämä on parametri toiselle rekursiiviselle kutsulle, joka vastaa C-koodin kutsua fibo(n - 2). Tämän kutsun tulos tulee taas rekisteriin rax.

Lopuksi koodi laskee yhteen rekisterien rax ja rbx arvot, joista tulee aliohjelman paluuarvo rekisteriin rax. Sen jälkeen täytyy vielä palauttaa rekisterin rbx alkuperäinen sisältö pinosta.

Aliohjelmakutsu C-kielessä

Kun konekielinen aliohjelma on toteutettu System V ABI -mallin mukaisesti, voimme kutsua aliohjelmaa suoraan esimerkiksi C-kielisestä ohjelmasta.

Esimerkiksi seuraava koodi toteuttaa aliohjelman calc_sum, joka laskee lukujen summan annetulta väliltä:

calc_sum.asm

global calc_sum

section .text
calc_sum:
    mov rax, 0
calc_loop:
    cmp rdi, rsi
    jg calc_end
    add rax, rdi
    inc rdi
    jmp calc_loop
calc_end:
    ret

Tässä tiedoston alussa merkintä global calc_sum tarkoittaa, että aliohjelma calc_sum on kutsuttavissa tiedoston ulkopuolelta.

Voimme käyttää aliohjelmaa C-funktiona seuraavasti:

main.c

#include <stdio.h>

long calc_sum(int a, int b);

int main(void) {
    printf("%ld\n", calc_sum(1, 100)); // 5050
}

Tässä funktion calc_sum esittely kertoo, että koodin käytettävissä on tällainen funktio. Koodilla ei ole tietoa siitä, että funktio on toteutettu konekielisenä aliohjelmana, mutta se kuitenkin tietää, miten funktiota voi kutsua. Funktion varsinainen toteutus linkitetään mukaan ohjelman käännösvaiheessa.

Seuraavat komennot kääntävät ja linkittävät ohjelman:

$ nasm -f elf64 calc_sum.asm -o calc_sum.o
$ gcc main.c calc_sum.o -o main

Ohjelman debuggaus

Konekielisen ohjelman toimintaa voi tutkia käyttäen GDB-debuggeria. Debuggerin avulla pystyy suorittamaan koodin komento kerrallaan sekä tarkkailemaan samalla rekisterien ja muistin sisältöä.

Ennen debuggerin käyttämistä ohjelma kannattaa kääntää -g-lipulla, jolloin NASM lisää mukaan debug-tietoa:

$ nasm -f elf64 -g test.asm -o test.o && ld test.o -o test

Seuraava komento käynnistää debuggerin:

$ gdb ./test

Aluksi voimme antaa debuggerille seuraavat komennot, jotka avaavat näkymän koodiin ja rekistereihin sekä määrittelevät ohjelman alkukohdan:

layout asm
layout regs
break _start

Tämän jälkeen voimme käynnistää ohjelman seuraavasti:

run

Debuggerissa komento ni liikkuu koodissa eteenpäin yhden komennon. Komento si puolestaan siirtyy tarkastelemaan aliohjelman koodia. Näiden komentojen avulla voimme käydä koodin läpi komento kerrallaan.

Voimme tutkia pinon sisältöä esimerkiksi seuraavasti:

x/10gx $rsp

Tämä komento näyttää pinon 10 ylintä 64-bittistä arvoa.

Käytännössä ohjelman debuggaus voi näyttää seuraavalta: