10.08.2021

Milloin dynaaminen muistinhallinta ei ole hyvä idea?

Yleensä tietokoneohjelmissa on totuttu ajatukseen, että muistia on riittävästi. Jos ohjelmalta loppuu muisti, se pyytää sitä lisää käyttöjärjestelmältä. Jos käyttöjärjestelmältä loppuu muisti, se päättää ohjelman suorituksen tai kriittisessä tapauksessa jonkun muun ohjelman suorituksen.

Joskus tilanne on se, että muistia ei ole paljon eikä ohjelma saa missään tapauksessa kaatua muistin loppumiseen. Voimme ajatella esimerkiksi sydämen tahdistajaa.

Myös erittäin kriittisessä palvelinymäristössä on edullista, ettei muistia käytetä tarpeettomasti dynaamisesti. Jos dynaamisesti varattu muisti loppuu, pyyntö saada sitä käyttöjärjelmältä lisää voi aiheuttaa muutaman millisekunnin pysähdyksen väärässä paikassa. Puhumattakaan roskienkeruun kymmenistä tai jopa sadoista millisekunneista.

Rustin normaali muistinhallinta

Rust normaalisti säilyttää muistissa olevia tietoja kolmessa paikassa:

Jos tiedämme kuinka syvälle funkiot voivat kutsua toisiaan, tiedämme pinon maksimikoon. Pinon muisti voi loppua vain, jos funkiot kutsuvat itseään (suoraan tai epäsuorasti) eli ne tekevät rekursiivisia kutsuja. Pinon ylivuoto huomataan.

Rustissa ei ole roskienkeruuta. Kieli takaa, ettei dynaamisesti varattuja käyttämättömiä muistialueita voi unohtua muistiin.

Rust-ohjelmointi ilman dynaamista muistia

Suurimmassa osassa ohjelmointia voidaan selvitä lähes yhtä hyvin ilman dynaamisesti varattuja muistiohjekteja. Kaiken tarvittavan muistin koko on tiedettävä silloin käännösaikana.

Rustin standardikirjasto on jaettu kahteen osaan

Normaalisti Rust käyttää vain std-kirjastoa, joka osanaan jakaa tarpeelliset coren toiminnot.

Jos halutaan selvitä ilman heappia, ohjelmatiedostoon lisätään attribuutti

#![no_std]

Ilman standardikirjastoa

Rekursion muuttaminen iteraattoriksi

Funktio, joka laskee Fibonaccin lukuja Rustilla rekursiivisesti on esimerkiksi tällainen:

fn fibonacci(n: u32) -> u32 {
    match n {
        0 => 1,
        1 => 1,
        _ => fibonacci(n - 1) + fibonacci(n - 2),
    }
}

Fibonaccin luku on siis luku, joka on kahden edeltävän Fibonaccin luvun summa.

1, 1, 2, 3, 5, 8, 13, ...

Jos tämä käännetään suoraviivaisesti konekoodiksi, jokainen kutsu aiheuttaa kaksi uutta rekursiivista kutsua lisäten pinon kokoa. Rekursiiviset funktiot voivat hyvinkin kasvattaa pinon koon hallitsemattomasti niin isoksi, että kohdekoneen muisti loppuu.

Kääntäjä yleensä poistaa häntärekursion eli jos jokaisen haaran lopussa kutsutaan rekursiivisesti funktiota itseään, funktiokutsu korvataan silmukalla. Edellisestä ohjelmasta kääntäjä optimoi toisen rekusiivisen kutsun silmukaksi, mutta ohjelma on kirjoitettavissa siten, että kummatkin kutsut optimoidaan pois. Ohjelman on kuitenkin tarkoitus olla esimerkki rekursiosta, joka voi siis olla paljon monimutkaisempaa kuin tässä esimerkissä, joten tämä ei nyt ole olennaista.

Saman funktion tekeminen iteraattorina on monimutkaisempaa, mutta sen tarvitsema tila on täysin staattinen ja käännösaikana tiedossa. Lisäksi iteraattoria voi käyttää hyvin monipuolisesti Rustin funktioilla.

Rustin itertools crate voidaan ottaa käyttöön ilman featurea use_std (päällä oletuksena), jolloin käytettävissä on vain toiminnot, jotka eivät tarvitse heappia. Suurin osa työkaluista on kuitenkin käytettävissä. Vain unique- ja group-tyyppiset operaatiot jäävät pois.

struct Fib {
    previous: usize,
    current: usize,
}

impl Fib {
    fn new() -> Fib {
        Fib {
            previous: 0, // Initialize fibonacci(0) = 0
            current: 1, // Initialize fibonacci(1) = 1
        }
    }
}

impl Iterator for Fib {
    type Item = usize;
    fn next(&mut self) -> Option<Self::Item> {
      let (p, c) = (self.previous, self.current);
      self.previous = c;
      self.current = p + c;
      Some(c)
    }
}

fn main() {
    for n in Fib::new().take(10) {
        println!("{}", n);
    }
    println!("{}", Fib::new()
        .filter(|x| (x % 2) == 0)
        .nth(9)
        .unwrap());
}

Tämä ohjelma luo iteraattorin, joka palauttaa Fibonaccin luvut järjestyksessä.

Iteraattorilla on helppo tehdä paljon monimutkaisempia juttuja kuin pelkällä funktiolla tai silmukalla. Iteraattori litistää ohjelmassa usein olevan monimutkaisen hiearkian yksinkertaiseksi peräkkäiseksi käsittelyksi.

Esimerkkiohjelma tulostaa ensin kymmenen ensimmäistä (take(9), ensimmäinen on nolla) fibonaccin lukua. Sitten uudella iteraattorilla valitsemme kymmenennen parillisen Fibonaccin luvun

Ensin .filter() valitsee parilliset luvut eli ne, jotka ovat kahdella jaollisia, kahden jakojäännös on nolla. Sitten nth valitsee kymmenennen arvon lopputuloksesta (laskenta alkaa nollasta kuten taulukoillakin, joten kymmenes elementti on nth(9)). Lopputulos on tyyppiä Option<usize>, koska iteraattori voi viestittää loppumisesta option arvolla None. Tässtä tapauksessa iteraattori ei voi loppua. Luku n täytyy kuitenkin lopuksi ottaa ulos optiorakenteesta Some(n) funktiolla unwrap().

Iteraattorin kuluttama muistimäärä on vakio ja pieni koko läpikäynnin ajan. Yleensä se on yhtä tehokas kuin silmukkarakenne, mutta sillä on paljon helpompi tehdä operaatioiden monimutkaisia ketjutuksia.

Heapless-tietotyypit

Rustin kirjastoissa on mukana heapless-crate joka sisältää tavallisimmat dynaamiset tietotyypit kuten Vec, String ja IndexMap sellaisina versioina, että niiden maksimikoko annetaan koodissa eikä tätä kokoa voi muuttaa. Tällöin niitä voi käyttää ilman dynaamista muistinhallintaa.

Seuraava koodi on kuin tavallinen Vec-vektori, mutta vektori on pinossa, ja sen maksimikoko on kahdeksan alkiota.

use heapless::Vec;

let mut v: Vec<u8, 8> = Vec::new();
v.push(3).unwrap();

Tätä kirjastoa voidaan huoletta käyttää sulautetussa järjestelemässä, jos tiedetään, ettei vektorin koko koskaan nouse yli kahdeksaan.

Pääohjelma, joka ei tarvitse dynaamista muistia

Useissa ohjeissa väitetään, että #[no_std] ratkaisee helposti sen, ettei dynaamista muistinhallintaa käytetä. Tämä valitettavasti pätee vain kirjastoihin. Pääohjelman, joka ei tarvitse dynaamista muistinhallintaa, tekeminen vaatii paljon lisää vaivaa.

Linux ei nykytilanteessa kykene helposti tuottamaan omaan käyttöön ohjelmia, jotka selviäisivät ilman dynaamista muistinhallintaa. Sen sijaan se osaa kyllä ristikääntää moneen sulautettuun ympäristöön ilman muistinhallintaa olevia ohjelmia aivan sulavasti.

Tällä hetkellä #[no_std] käynnistää kaikki toiminnot, jotka olettavat, että ohjelma on menossa ympäristöön, jossa ei ole ollenkaan käyttöjärjestelmää. Ohjelman on itse tarjottava poikkeustilanteiden käsittely ja käyttöjärjestelmätön ohjelman käynnistys.

Nämä toiminnot ovat melko epästabiileja ja dokumentaatio ei ole täysin ajan tasalla.

Panic

Jos pääohjelmassa on no_std, sen on itse tarjottava funktio, jota kutsutaan, jos ohjelma päätyy panic-virheeseen.

use core::panic::PanicInfo;

#[panic_handler]
fn panic(_panic: &PanicInfo) -> ! {
    loop {}
}

Huutomerkki paluuarvona kertoo, ettei tämä funktio koskaan voi palata. Tämä toteutus jää yksinkertaisesti ikisilmukkaan paniikin tapahtuessa.

eh_personality

Toinen funktio, joka tarvitaan on nimeltään eh_personality, mutta tapa, jolla sen toteutuksen yksinkertaisesti kiertää on erilainen.

eh_personality vapauttaa panic-tapauksessa varatun muistin mahdollisuuksien mukaan. Jos panic-funtio on ikisilmukka, tästä ei tarvitse kovin paljon välittää.

Tarve kutsua eh_personality-funktiota poistuu, jos projektin asetustiedostoon Cargo.toml lisätään tähän määräävät asetukset.

[profile.dev]
panic = "abort"

[profile.release]
panic = "abort"

main()

Teoriassa Rustissa pitäisi voida käyttää no_std -asetusta esimerkiksi Linuxissa ajettavassa ohjelmassa. Se on kuitenkin käytännössä hyvin vaikeaa.

no_std -asetuksen kanssa käyttäjän on itse hoidettava myös ensimmäisen funktion kutsuminen. Teoriassa tämän pitäisi olla vaadittu vasta, jos määritellään myös no_main, mutta kokeilujeni perusteella jo no_std vaatii main-funktion muuttamisen.

Tämä pitää hoitaa käyttöjärjestelmästä riippuen suunnilleen seuraavasti:

#![no_std]
#![no_main]

#[no_mangle]
pub extern "C" fn _start() -> ! {
  ...
}

missä no_mangle ja pub extern "C" takaa, että _start on linkkerille ulospäin näkyvä C-kutsukonventiolla kutsuttava funktio. Käyttöjärjestelmä tms. pitää sitten saada kutsumaan tuota funktiota.

Linkkaus

Ja jäljellä on vielä suurin ongelma. Rust-kääntäjässä ei ole valmiina kohdearkkitehtuuria "ei käyttöjärjestelmätukea" esim. Linux-ympäristöön. Standardi käännös-target x86_64-unknown-linux-gnu yrittää yhdistää ohelmaan C-kirjastoa, mikä epäonnistuu, koska std-kirjastoa ei ole mukana.

Linkkaus onnistuu, jos käännöskohde on esimerkiksi sulautettu ARM-prosessori ilman käyttöjärjestelmää. Esim. thumbv7em-none-eabihf

Linuxille voidaan määritellä custom käännös-target. Nykyisen käännös-targetin asetukset saa näkyviin komennolla

rustc +nightly -Z unstable-options --target=x86_64-unknown-linux --print target-spec-json

Asetukset saa yksinkertaisesti --print -valitsimella. Mutta tämä on käytettävissä vain, jos on valittu -Z unstable-options. Mikä taas on saatavissa tällä hetkellä vain nightly releasen kääntäjässä.

Lisätietoja