メモリのアロケーティング

Unique を使用することで、 Vec の重要な機能に関して (そして実に std の全てのコレクションにおいて) 問題が発生します。すなわち、空の Vec は実際に、何もアロケートしていないのです。ですからもしアロケート出来ないだけではなく、 ptr にヌルポインタを代入出来ないとしたら、 Vec::new で何をすればいいのでしょうか? そうだ、単純にそこに何か他のゴミを突っ込みましょう!

これは全く問題ありません。なぜなら、 cap == 0 が既に、アロケーションがないことを示す番兵となっているからです。もはやこれを特別扱いする必要もありません。なぜならほとんどすべてのコードで、結局は cap > len か len > 0 を通常確かめる必要があるからです。伝統的に Rust では、 0x01 を突っ込んでいます。標準ライブラリでは実際にこれを alloc::heap::EMPTY として公開しています。 null を使ってしまうとコンパイラが悪さをしてしまうけれども、実際のアロケーションが存在しないために heap::EMPTY を使用したい箇所がかなり多く存在します。

それでも全ての heap の API は、 heap_api フィーチャの下で、全くアンステーブルです。自ら heap::EMPTY を定義してしまうことも出来るでしょうが、結局 heap の他の API を使いたくなるため、単にその API を依存関係に追加しましょう。

こうなります:

#![feature(alloc, heap_api)]

use std::mem;

use alloc::heap::EMPTY;

impl<T> Vec<T> {
    fn new() -> Self {
        // まだ ZST を扱う準備が出来ていません
        assert!(mem::size_of::<T>() != 0, "We're not ready to handle ZSTs");
        unsafe {
            // EMPTY を欲しい実際のポインタ型にキャストする必要があります。
            // 推論してもらいましょう。
            Vec { ptr: Unique::new(heap::EMPTY as *mut _), len: 0, cap: 0 }
        }
    }
}

コードの中に、assert を入れました。サイズが 0 の型は、コード全体において何か特別な処理をする必要があり、この問題を今は後回しにしたいためです。この assert がないと、コードの下書きにおいて、なにか非常にまずいことを起こしてしまいます。

次に、本当にスペースがほしいときに、実際に何をすればいいかを考える必要があります。そのためには、 heap の他の API を使用する必要があります。基本的にこれらによって、 Rust のアロケータ (デフォルトでは jemalloc) と対話できるようになります。

また、メモリ不足 (out-of-memory, OOM) の状態に対処する方法も必要です。標準ライブラリでは、単に abort intrinsic を呼びます。これは単純に不正な命令を呼び出して、プログラムをクラッシュさせます。なぜパニックではなくアボートさせるかというと、巻き戻しはアロケーションを起こす事があるため、アロケータが "なあ、もうメモリがないぜ" と帰ってきたときに巻き戻しを行なうのはまずいからです。

もちろん、通常ならほとんどのプラットフォームにおいて、実際にメモリ不足に陥ることはないため、これはちょっと馬鹿げています。オペレーティングシステムは、何らかの理由でアプリケーションが全てのメモリを使用しているなら、そのアプリケーションを他の手段によって多分 kill するでしょう。 OOM になってしまう、もっともあり得る場合というのは単に、信じられないくらいのメモリ量をいっぺんに確保しようとする場合です (例: 理論上のアドレス空間の半分) 。ですからパニックしても多分問題なく、何も悪いことは起きません。それでも、なるべく標準ライブラリに似せるため、ここでは単にプログラム全体を kill します。

intrinsic を使いたくないと述べました。ですので、 std で行なっていることと、全く同じことをすることは出来ません。代わりに、 std::process::exit を適当な値と共に呼び出します。


#![allow(unused)]
fn main() {
fn oom() {
    ::std::process::exit(-9999);
}
}

よし、これで Vec の伸長のコードを書くことが出来ます。欲しいロジックは大体以下のようなものです。

if cap == 0:
    allocate()
    cap = 1
else:
    reallocate()
    cap *= 2

しかし、 Rust が唯一サポートしているアロケータ API は本当に低レベルなものですので、追加の作業がかなり必要です。また、本当に大きいアロケーションや、空のアロケーションの際に起こる、特別な状況に対してガードする必要もあります。

特に ptr::offset は、沢山の問題を引き起こします。なぜならこれは、 LLVM の、 GEP インバウンド命令のセマンティクスを持っているからです。もしあなたが幸運にも、この命令に対処したことがない場合、こちらが GEP に関する基本的な事柄です: エイリアス分析、エイリアス分析、エイリアス分析。コンパイラが最適化をする際、データの依存関係や、エイリアシングを推論できるということは、本当に重要なのです。

単純な例として、以下のコード片を考えてみましょう。


#![allow(unused)]
fn main() {
let x = &mut 0;
let y = &mut 0;
*x *= 7;
*y *= 3;
}

もしコンパイラが、 x と y がメモリ上の別の場所をそれぞれ指していると証明できるのなら、理論的には、これらの 2 つの命令は並列に行なうことが可能です (例: 異なるレジスタにロードして、個別に操作する) 。しかしながら、コンパイラは一般的にこれをすることが出来ません。なぜなら、 x と y がメモリ上の同一の場所を指しているのなら、操作を同じ値に対して行なわなければならず、単に最後、統合することは不可能だからです。

GEP インバウンドを使用する際、実行しようとしているオフセットは、単一の "アロケートされた" エンティティの境界内に収まると、 LLVM にはっきりと伝えることになります。 LLVM を使うことによる究極の利点は、 2 つのポインタが異なるオブジェクトを指すと分かっている時、これらのポインタの全てのオフセットも、エイリアスではないということが分かるということです (なぜならメモリ上のどこかランダムな場所を指さないと分かっているからです) 。 LLVM は、 GEP オフセットを扱うために激しく最適化されていて、インバウンドオフセットは全ての中で最良のものです。ですからなるべくこれらを使うことが重要です。

これが、 GEP についてです。ではこれが、どのような問題を引き起こすのでしょうか?

第一に、配列のインデックス指定では符号なし整数を指定しますが、 GEP (そして結果として ptr::offset も) では符号付き整数を受け取ります。これはつまり、配列のインデックス指定では有効であろう値の半分が、 GEP ではオーバーフローしてしまい、実際に間違った方向に進んでしまうのです! ですから全てのアロケーションを isize::MAX 個の要素に制限しなければなりません。これは実際には、バイトサイズのオブジェクトに関してのみ、心配する必要があります。なぜなら、例えば isize::MAX 個以上の u16 などでは、明らかにシステムのメモリを使い果たしてしまうでしょう。しかし、何らかの、 isize::MAX 個以下のオブジェクトを持つ配列をバイト群と再解釈するような、微妙なコーナーケースを避けるため、 std では全てのアロケーションを isize::MAX バイトに制限しています。

Rust が現在サポートしている 64 ビットのターゲットでは、恣意的に、 64 ビットのアドレス空間全体よりも遥かに少なく制限されています (現代の x64 プラットフォームでは、 48 ビットのアドレスしか使用可能ではありません) 。ですから単純に、最初にメモリ不足になると考えて良いです。しかし 32 ビットのターゲットでは、特に追加のアドレス空間を使用する拡張に対して (PAE x86 や x32) 、理論的には isize::MAX バイト以上のメモリをアロケートしてしまうことが可能です。

しかしながら、これはチュートリアルですので、ここではベストを尽くしません。単に、プラットフォーム特有の cfg 等を使用するのではなく、状況に関わりなくチェックします。

心配しなければならない他のコーナーケースは、空のアロケーションです。空のアロケーションには 2 種類あります。全ての T における cap = 0 と、サイズが 0 の型における cap > 0 です。

これらは結局、 LLVM が意味する "アロケートされた" 状態ですので、扱いにくいです。 LLVM におけるアロケーションの概念は、我々が普段使う概念よりも遥かに抽象的です。 LLVM は異なる言語のセマンティクスや、カスタムアロケータを扱う必要があるため、アロケーションに深入り出来ないのです。その代わり、アロケーションの背後にある主要な考えは "他のものと重ならない" という事です。つまり、ヒープアロケーションやスタックアロケーション、そしてグローバルなアロケーションは、ランダムに重なることはありません。ええ、これはエイリアス分析についてです。ですから、 Rust は一貫性を保つ限り、アロケーションの概念に関しては技術的に、ちょっと高速に、ちょっと緩く、行なうことが出来ます。

空のアロケーションの場合について戻りましょう。ジェネリックなコードの結果、 0 のオフセットが欲しい場合がいくつかあります。そうすると問題はこうなります。すなわち、これを行なうことは、一貫性があるのでしょうか? 例えばサイズが 0 の型の場合、任意の要素数による GEP インバウンドオフセットを行なうことは、実に一貫性があると結論付けました。これは実行時には no-op です。なぜなら、全ての要素はスペースを消費せず、そして 0x01 に無限の数の、サイズが 0 の型がアロケートされているとしても問題ないからです。どのアロケータも、絶対にそのアドレスにはアロケートしません。なぜなら、アロケータは 0x00 にはアロケートせず、一般的にバイト以上のある最小のアラインメントにアロケートするからです。また一般的には、メモリの最初のページ全体は、アロケートされることに対し結局保護されています (多くのプロットフォームでは 4k 全体) 。

しかしながら、サイズが正の型についてはどうでしょうか? これはちょっとトリッキーです。一般には、 0 のオフセットでは LLVM には何の情報も行き渡らないと論ずる事が出来ます。すなわち、アドレスの前か後ろかのどちらかに要素があるけれども、どっちなのかはわからないということです。しかし、これによって悪いことが起きると保守的に見なすことを選びました。ですからこれらの場合に対しては、明示的にガードします。

ふー

よし、ナンセンスな物を退けましたので、実際にメモリをアロケートしてみましょう。

fn grow(&mut self) {
    // これは本当に繊細なので、全部アンセーフにしましょう
    unsafe {
        // 現在の API では、大きさとアラインメントを手動で指定する必要があります。
        let align = mem::align_of::<T>();
        let elem_size = mem::size_of::<T>();

        let (new_cap, ptr) = if self.cap == 0 {
            let ptr = heap::allocate(elem_size, align);
            (1, ptr)
        } else {
            // 不変条件ですので、 `self.cap < isize::MAX` と見なすことが出来ます。
            // ですからチェックする必要はありません。
            let new_cap = self.cap * 2;
            // 同様に、前にアロケートしたのでオーバーフローすることはありません
            let old_num_bytes = self.cap * elem_size;

            // 実際のキャパシティの大きさに関わらず、新しいアロケーションが
            // `isize::MAX` を超過しないか確認します。これは、必要なチェックである、
            // `new_cap <= isize::MAX` と `new_num_bytes <= usize::MAX` を
            // 組み合わせています。もっとも、例えば 32ビットプラットフォーム上では、
            // i16 の単一の Vec で、アドレス空間の 2/3 をアロケートすることは
            // できなくなっていますが。
            // Alas, poor Yorick -- I knew him, Horatio.
            // (訳注: シェイクスピアに登場する、ハムレットのセリフです)
            assert!(old_num_bytes <= (::std::isize::MAX as usize) / 2,
                    "capacity overflow");

            let new_num_bytes = old_num_bytes * 2;
            let ptr = heap::reallocate(*self.ptr as *mut _,
                                        old_num_bytes,
                                        new_num_bytes,
                                        align);
            (new_cap, ptr)
        };

        // もしアロケートや、リアロケートに失敗すると、 `null` が返ってきます
        if ptr.is_null() { oom(); }

        self.ptr = Unique::new(ptr as *mut _);
        self.cap = new_cap;
    }
}

ここでは特にトリッキーなことはしていません。単にサイズとアラインメントを計算し、掛け算を注意深くチェックしています。