2021-11-07

Rustのメモリ管理機能とその特徴

初出：技術評論社刊「ソフトウェアデザイン 2021年9月号」

先日、技術評論社よりRustのメモリ管理機能についての特集に寄稿させて頂きました。
この記事は自分が寄稿させていただいた記事をブログ用に一部推敲・加筆を加えたものです。
なお、ソフトウェアデザインでの特集ではより実践的な例でのメモリ管理についての解説もあるので、興味のある方は本誌のほうも手にとっていただければと思います。

プログラム言語におけるメモリ管理の課題

プログラミングにおける課題の一つとしてどうやってメモリ領域（ヒープ領域）を管理するかというものがあります。

C言語ではmalloc/free関数などを用いて手動でメモリを管理しています。
これらの関数はメモリアドレスを示すポインタを介してメモリ管理を行います。
malloc関数は必要なメモリ領域を確保してその先頭番地のポインタを返し、プログラム内ではその番地のメモリを読み書きし、使い終わったらfree関数にその番地を教えて解放する、という流れです。
この方式では、どのタイミングでメモリが操作されるかが明確なので実行時間やメモリ効率がいいのですが、人の手で毎回操作しないといけないので、プログラミングに複雑になりやすくミスを起こしやすいことが知られています。
例えば、ポインタの指し示す先のメモリがもう解放されていたり、他の用途で使われているのにもかかわらず値を読み書きしてしまうことがあります。
C++ではもう少し抽象化された形を用いていますが、基本的には自分で必要なタイミングでメモリの確保・解放を行う必要があり同様の課題を抱えています。

一方、Python・Rubyなどのスクリプト言語を中心に用いられているのがガベージコレクション（GC）という仕組みです。
この方式では実行環境が適当なタイミングで現在使用中のメモリの内容をチェックして、もう必要のないメモリを自動で開放するというものです。
この方式では、プログラマがメモリ解放のタイミングを指定する必要がなく、メモリ解放に関わるミスを防ぐことができます。
その一方で、GCを実行する際にプログラムを一時的に止める必要があったり、GCを走らせるまでは必要のないメモリを確保し続けたままになってしまうなど、実行時の効率が問題になるケースがあります。

Rustは所有権とライフタイムを利用することで、GCのような実行時のメモリ管理コストをなくし、かつ手動でのメモリ管理で起きがちなバグをコンパイラレベルで検知することができます。
この所有権とライフタイムがRustを学ぶ上での大きな壁の一つで完全に使いこなすのはかなり大変です。
かくいう筆者も、数年間Rustを書いていますが頻繁に頭を悩ませる問題であり、コンパイラに怒られながらなんとか直すということしながら書いています。
しかしながら、使いこなすことで安全性が高くかつ実行時コストが非常に少ないコードを書ける仕組みで、Rustが支持される理由の一つでもあります。

今回は所有権・ライフタイムの大まかな概念を見たあと、簡単なリスト構造を題材にこのメモリ管理機能を見ていきます。

Rustは何を保証するか

C言語などにおけるポインタをつかったメモリ管理は以下のような問題を引き起こすことが知られています。

• これからアクセスしようとしている領域がすでに解放済みだったり他のことに使われているなどの原因により不正なものになっている（ダングリングポインタ）
• すでに解放されているメモリ領域を誤ってもう一度解放してしまい未定義動作を引き起こす
• 確保した領域がもう使われていないにもかかわらず解放されない（メモリリーク）

Rustはガベージコレクションのような実行時でのメモリ管理ではない方法でこれらの問題を回避します。
Rustではポインタを使って値にアクセスすることは基本的にはありません（できないことはないのですがunsafeと呼ばれる特殊な操作になり、Rustが保証する安全性を損ないます）。
かわりに使うのが「参照」と「スマートポインタ」などの機能です。
これらがどのようにポインタで発生しうる問題を回避するかを見てみましょう

参照と借用

参照の概念を説明する前にまず「所有権（ownership）」の概念について簡単に見てみます。

Rustのにおける値は唯一の所有者（owner）が存在します。変数に値を代入すると、その変数が値の所有者になります。
同じ値に対して複数の所有者が存在することはできません。
所有者である変数のスコープが終了すると、その値は解放されます。
簡単な例を挙げましょう。

{
    let a = String::from("hello");
}
// ブロックの外に出たことで、aにはアクセスできなくなりaの持っていた値は解放される
println!("{}", a);  // この文はコンパイルエラーになる

関数呼び出しや他の変数に値を渡すために所有権を渡す（ムーブ）こともできます。その場合、もともとの変数は所有権を失うので使えなくなります。

let a = String::from("hello");
let b = a;

println!("{}", b);
// 下の文はもうaが使えないのでコンパイルエラーとなる
// println!("{}", a);

しかし、実際には関数呼び出しや構造体のメンバーとしてポインタのようなものを持ちたい場合など、所有権がまるまる渡ってしまうのは不都合な場面があります。
そこでRustでは一時的に値を「借用（borrow）」する、ということができます。このときできるのが「参照（reference）」です。
参照のイメージとしては制限付きのポインタのようなものです。
関数に参照を渡す例を下に示します。

// 呼び出し元から値を借用する関数
fn print_string(a: &String) {
    println!("{}", a);
}

fn main() {
    let a = String::from("hello world");

    print_string(&a);   // aの参照を渡している

    let b = a;          // 参照を渡すだけでは所有権は失われないので、bにムーブすることができる
    
    print_string(&a);   // aは所有権を失っているので参照はつくれず、コンパイルエラー
}

aを借用することで所有権を失わずに関数を呼び出していますが、所有権を失っている変数への参照をつくるといったことをするとコンパイルエラーとなります。
このように、参照は普通のポインタとは違い、不正な値への参照がないようコンパイラが保証してます。
そこで登場するのが「ライフタイム（lifetime）」という概念です。
ライフタイムとはその参照が有効となる期間のことで、これをコンパイラがチェックすることでダングリングポインタや解放済みの領域へのアクセスというものを防いでいます。
他の例を見てみましょう。C言語でのダングリングポインタの例として、関数内のローカル変数へのポインタを関数の返り値にしてしまう、というものがあります。
以下にC言語での例を示します。

#include<stdio.h>

typedef struct Point {
    int x;
    int y;
} point_t;

point_t* get_point(void) {
    point_t p = { 0, 0 };
    return &p;
}

void main(void) {
    point_t* p = get_point();
    printf("%d %d", p->x, p->y);
}

GCCを使いコンパイルすると、警告はでるもののコンパイルできてしまいます。
これを実行すると筆者の環境ではセグメンテーションフォルトになりました。ローカル変数はスタック上に確保されますが、関数が返るときに解放されてしまうので、呼び出し先（この例ではmain関数内）では使うことができません。

Rustで同じようなコードを参照で書こうとするとコンパイルエラーになります。

struct Point {
    x: i32,
    y: i32,
}

fn get_point<'a>() -> &'a Point {
    let p = Point {
        x: 0,
        y: 0,
    };
    &p
}

fn main() {
    let p = get_point();
    println!("{} {}", p.x, p.y);
}

突然返り値に'aというのが出てきましたが、これがライフタイムを表しています。今まではライフタイムを明示しなくてもコンパイラが自動的に判断できたのでつけなかったのですが、このように返り値として参照をつける場合は明示する必要があります。
同じライフタイムを持つ参照は同じ期間生存する必要があります。
コンパイラのエラーメッセージはこのようになります。

error[E0515]: cannot return reference to local variable `p`
  --> src/main.rs:12:5
   |
12 |     &p
   |     ^^ returns a reference to data owned by the current function

pはローカル変数なのでそこへの参照は返すことができない、と言われています。
つまりget_point関数の返り値の参照は関数外でも生存している必要がありますが、
ローカル変数はライフタイムが関数内で尽きてしまうため、関数外でも生きる参照にはなれない、ということです。

可変性

Rustの参照の他のおもしろい性質として、可変参照と普通の参照が区別されることでしょう。
実は今まで登場してきた普通の参照は参照先の値を変更することができません。
参照先の値を変更したい場合は&ではなく&mutとつけることで可変（mutable）参照を使う必要があります。
配列を使った例で見てみましょう。

// 可変参照をとることで、配列の中身を変更する
fn add_one(a: &mut Vec<i32>) {
    for i in 0..a.len() {
        a[i] += 1;
    }
}

fn main() {
    let mut a = vec![0, 1, 2];
    add_one(&mut a);
    println!("{} {} {}", a[0], a[1], a[2]);
}

vec!マクロを使ってVecというRust標準の動的配列をつくり、その可変参照を関数に渡しています。この&mutを&にするとコンパイルが通りません。

可変参照と通常の参照を分けることによって例えば以下のようなケースでダングリングポインタを防ぐことができます。

fn main() {
    let mut a = vec![0, 1, 2];
    let x = &a[0];
    a.clear();  // Vecのclear関数は可変参照をとる
    
    println!("{}", x); // xの指す先はすでに解放されている
}

配列aの先頭要素への参照をxとして、その後clearを呼ぶことで配列の中身をすべて消します。
その後、xを使い解放されたはずの先頭要素を出力しようとしています。これはコンパイルされてしまえばダングリングポインタということになってしまいます。
実際にはこのコードは以下のようなエラーが出てコンパイルが失敗します。

error[E0502]: cannot borrow `a` as mutable because it is also borrowed as immutable
 --> src/main.rs:5:5
  |
4 |     let x = &a[0];
  |              - immutable borrow occurs here
5 |     a.clear();  // Vecのclear関数は可変参照をとる
  |     ^^^^^^^^^ mutable borrow occurs here
6 |     
7 |     println!("{}", x); // xの指す先はすでに解放されている
  |                    - immutable borrow later used here

実は可変な借用をする場合、その値に対する他の参照は存在できないというルールがあります。
今回の場合、xはprintln!で使われるあいだまでライフタイムがあるにもかかわらず、その間で可変参照をつくろとしています。
a.clear()は一見するとよくわからないかもしれませんが、Rustのメソッド呼び出しをする場合、その値を借用することで呼び出されます。
clear関数は以下のような定義になっています。

pub fn clear(&mut self)

selfというのがそのメソッド呼び出しをしているインスタンスで、その可変参照をとるということです。

リスト構造を書いてみる

もう少し実践的な例としてリスト構造をRustで書くことを考えます
今回は関数型言語でよく見かけるconsを使ったリストというのを書いていきます。consとは２つの値のペアからつくられるリストで、関数型言語だとこういうような書き方をします。

(2, (5, (3, nil)))

これは[2, 5, 3]という連結リストのようなものです。各ノードは左側をcar、右側をcdrと呼びます。
リストは空の場合nil、そうでない場合先頭の値をcarに持ち、先頭を除く残りのリストをcdrとして持つ再帰的な構造になっています。

これをRust風に書いていきたいと思います。なお、このようなリストをRustで使うことはあまりなく、Vecのような標準で備わっている型を通常は使います。
リストは空の場合はnilでそうでない場合はペアになっているという２つのパターンがあります。このような構造をあらわすにはenum（列挙型）を使うと便利です。

enum List {
    Cons(i32, List),
    Nil,
}

ただし、これはこのままだと定義できません。なぜならList型がそのままList内のメンバーに使われてしまっているからです。
こうしてしまうとList型が無限のサイズを持たなければなりません。C言語ではこういう場合はポインタを使うように、今回は参照を使って書き直してみます。
参照はポインタのようなもの、と先ほど説明しまいたが、コンパイルされると内部的には参照先の値へのアドレスとなります。
そのため、値の参照先の型によらずアドレス分のサイズしか必要ありません。

enum List<'a> {
    Cons(i32, &'a List<'a>),
    Nil,
}

use crate::List::{Cons, Nil};

fn main() {
    let list = Cons(2, &Cons(5, &Cons(3, &Nil)));
}

参照に明示的にライフタイムを書かなければならないことに注意してください。
参照はポインタと同じように内部的にはその値の先のアドレスを持つだけなので、List型のサイズによらずアドレスの値の分で一定なので先ほどみたいに無限のサイズにならずにすみます。
また今回は簡単のためリストの中身を書き換えるということは考えないことにします。

とりあえずリストは定義できました。次にいろいろな操作を書いてみましょう。
まずはリストの内容を全て出力する関数を書いてみます。

fn print_list(list: &List) {
    match list {
        Cons(val, ls) => {
            println!("val: {}", val);
            print_list(ls);
        }
        Nil => {}
    }
}

fn main() {
    let list = Cons(2, &Cons(5, &Cons(3, &Nil)));
    print_list(&list);
}

enumに対してはこのようにパターンマッチを使った操作をすることができます。
consの場合はその値を出力して、残りのリストに対して再帰的にprint_listを呼び出し、nilに到達したら終了します。

出力結果は以下のようになります。

val: 2
val: 5
val: 3

さて、このリストを新たにつくる関数を考えてみましょう。
例えばこのリストの末尾に新たな要素を付け加えたリストを新たにつくりたいと思います。

関数はリスト受け取って空リストならその新たな要素１つのみを含むリストを返し、consなら残りのリストに対して関数を再帰的に呼び出し、
その結果をcdrにした新しいconsを返すことで実現できそうです。

fn append<'a>(list: &'a List, val: i32) -> List<'a> {
    match list {
        Cons(x, ls) => {
            Cons(*x, &append(ls, val))
        },
        Nil => {
            Cons(val, &Nil)
        }
    }
}

fn main() {
    let list = Cons(2, &Cons(5, &Cons(3, &Nil)));
    let list2 = append(&list, 7);
    print_list(&list2);
}

しかし、これは以下のようなコンパイルエラーになってしまいます。

error[E0515]: cannot return value referencing temporary value
  --> src/main.rs:22:13
   |
22 |             Cons(*x, &append(ls, val))
   |             ^^^^^^^^^^---------------^
   |             |         |
   |             |         temporary value created here
   |             returns a value referencing data owned by the current function

再帰呼出ししてつくった値が関数内でしか生存しないので、ライフタイムが合わずエラーが出ています。
このように、参照のみをつかってデータ構造を定義しようとするのは非常に難しいです。どうしたらよいのでしょうか？

C言語の経験がある方は、このような場合メンバーはポインタで持つと思うのですが、その値をつくるときにmalloc関数などを使いヒープ領域から値をとってくると思います。
Rustでもヒープ領域を扱う方法はもちろんあります。例えば、String型は内部的にはヒープ領域を使っています。
C言語の場合、malloc関数などでヒープ領域に確保された領域をポインタで指し示しますが、Rustでは「スマートポインタ」と呼ばれるものを使い安全にヒープ領域を扱います。

スマートポインタを使ったヒープ領域の活用

スマートポインタという言葉はC++でも使われているので知っている方もいるかもしれません。
普通のポインタとは違い、参照のように不正な操作を防ぐための仕組みが備わっています。
スマートポインタといってもRustには何種類か備わっているのですが、まずは一番（？）スタンダートなBoxというのを見てみましょう。

fn main() {
    let x = 5;
    let mut boxed = Box::new(x);

    println!("boxed = {}", boxed);
    *boxed += 3;
    println!("x = {}, boxed = {}", x, boxed)
}

xをつかってboxedという値をつくりました。この値はヒープ上に確保されて、参照のように使うことができます（Derefと型強制という仕組みでおこなわれているのですが詳細は割愛します）。
xの値はコピーされているので、boxedを変更してもxの値は変化しません。

これを用いて先程のListの例を書き換えてみましょう。Boxも内部的にはポインタと同じようにその先が指し示す構造によらず一定のサイズで済む型です。

enum List {
    Cons(i32, Box<List>),
    Nil,
}

use crate::List::{Cons, Nil};

fn print_list(list: &List) {
    match list {
        Cons(val, ls) => {
            println!("val: {}", val);
            print_list(ls);
        }
        Nil => {}
    }
}


fn main() {
    let list = Cons(2, Box::new(Cons(5, Box::new(Cons(3, Box::new(Nil))))));

    print_list(&list);
}

これは正しくコンパイルされ、先ほどと同じ出力結果を得られます。
先程断念した末尾に新たな要素を付け足したリストを返す、という関数も簡単に実現できるようになります。

fn append(list: &List, val: i32) -> List {
    match list {
        Cons(x, ls) => {
            Cons(*x, Box::new(append(ls, val)))
        },
        Nil => {
            Cons(val, Box::new(Nil))
        }
    }
}



fn main() {
    let list = Cons(2, Box::new(Cons(5, Box::new(Cons(3, Box::new(Nil))))));
    let list2 = append(&list, 7);

    print_list(&list2);
}

今度はコンパイルできて以下のような出力結果が得られます。

val: 2
val: 5
val: 3
val: 7

なぜ今回は問題がなかったかというと、Box::newでつくられた値を借用するのではなく、ムーブによって所有権ごと渡されているからです。
内部的にも値の中身はヒープ領域にあるので関数から出てしまっても保持されているので問題ありません。

メモリ解放について

関数内のローカル変数の場合、その関数が終わるときにスタックが破棄され値も解放されますが、Boxのようにヒープを使う場合どのように解放されるのでしょうか。
実はBoxにはDropというトレイト（C++のインターフェースのようなもの）が実装されていて、その値がスコープから出たときにメモリが解放されるような実装がされています。
所有権システムによりその値に紐付いている変数は複数存在することはできないので、Dropトレイトによって実装されたメモリ解放の動作が同じBoxのインスタンスに対して働くことはありません。
また、自分たちでわざわざどこでメモリを解放するかを明示する必要もありません。

Rustのメモリ管理の弱点

ここまでRustでのメモリの扱いについて一通り見てきました。
Rustがこれらの仕組みを使いメモリを安全にアクセスできるというのがわかったと思います。

一方で、いくつかの弱点もあります。まず、可変な参照を考慮すると問題が複雑になることです。
可変参照は複数つくれないことを説明しましたが、現実には複数の値に同じ値を操作するための参照を持ちたい場合というのは結構あります。
例えば可変な双方向連結リストがそれにあたります。リストの各ノードは前後の要素に対する参照をもつような実装になりますが、そうするとあるノードに対しての可変参照が前のノードと後ろのノードのそれぞれが持つことになってしまいます。
一応、そういうケースをなんとかする構造体もあるのですが、普通のポインタよりかはオーバーヘッドがつきます。

またRustは実はメモリリークが起きない保証はしていません。
確かにBoxなどは自動的にメモリを開放する仕組みが備わっていますが、意図的にそういうものを無効にする関数があります（std::mem::forget）。
普通、Rustの安全性の保証を無視する関数はunsafeとマークされるのですが、そのような関数はunsafeとされていません。

このように、Rustのメモリ管理も万能ではありません。しかしながら、生のポインタを使うよりかはずっと安全で、GCありの言語よりかは扱いにくいと思いますが、その分高いパフォーマンスを得ることができます。

参考文献

• The Rust Programming Language
• The Rustonomicon
• 「実践Rust入門」（技術評論社）

Rust