LoginSignup
12
5

More than 5 years have passed since last update.

D言語Advent Calendar 2018Day 3
@lempiji

D言語で作る安全で効率的なAllocatorについて

Last updated at Posted at 2018-12-02

はじめに

さて、今年もDConf 2018が行われました。
色々な発表がありましたが、その中から印象的だった Alexandru Jercaianu さんが発表された安全で効率的なAllocatorの話について簡単に解説したいと思います。意訳と抜粋引用であり翻訳ではないのでご注意ください。。

なお、解説じゃなくて原本読むぞという方は

にそれぞれありますので参考としてください。

内容は英語ですが、大半がコードだったり図だったりフリーザ様の挿絵があったりするので雰囲気で読めると思います。

TL;DR

  • パフォーマンスを求めるなら独自のメモリ管理が必要
    • 安全や生産性を重視するなら素直にGCを使おう
    • がんばるなら std.experimental.allocator を使おう
    • あとはdubに emsi_containers ってパッケージがあるのでこれもオススメ
  • Allocatorには色々難しい問題があるのでよく考えよう
  • メモリ管理戦略としてLayout-baseという手法の解説
    • 型ベースではなく、同じレイアウトなら同じAllocatorを共有させることで、安全性を保ったままメモリを再利用、断片化率を下げて効率アップ
    • 要するにObjectPoolがちょっと汎用化されたイメージ
  • D言語のメタプログラミングつよい
    • std.meta があれば __traits と組み合わせるだけで簡単にレイアウト計算は作れる

Allocatorとは？

D言語にはガベージコレクタ(GC)を使ったメモリ管理機能がありますが、ゲームなど処理時間がシビアな場合は高速化のためにさらに細かい独自のメモリ管理を行う場合があります。

このときにメモリ管理をする役割をAllocator(アロケーター)と呼びます。
一般には「割り当てるもの」であるため、GCもAllocatorの一種と言えなくもありません。

いくつか特殊な操作はありますが、Allocatorに求められることは大きく2つで、

  • 「欲しい」と言われたら、要求サイズのメモリを返す
  • 「もう使わない」と言われたら破棄する

ということだけです。

またスライドからの抜粋ですが、独自のAllocatorを作る際の基本機能を表すと以下のようなコードになります。

struct MyAllocator {
    // 必須機能である割り当てと破棄
    void[] allocate(size_t size);
    bool deallocate(void[] b);

    // 任意機能
    void[] alignedAllocate(size_t s, uint a);
    bool reallocate(ref void[] b, size_t newSize);
    bool expand(ref void[] b, size_t delta);

    // 他にも多くの基本的な操作がある…
}

Allocatorの例

独自のAllocatorであれば処理高速化のため、最初にまとめてメモリを確保、それを切り売りするように使っていく、という戦略が多いかと思います。OSのメモリ確保は遅いので、1回まとめて取っておけば速くなるだろう、という発想ですね。
そういった戦略毎に独自のAllocatorを作ることになります。

Dの標準ライブラリでは std.experimental.allocator という試験的なモジュールが提供されており、ここですでにいくつかのAllocatorが提供されています。
このモジュールには BuildingBlock と呼ばれる構成パーツがあり、それを組み合わせて細かくチューニングできるようになっています。

スライドでは基本的なAllocatorがいくつか挙げられていますが、ざっくり説明すると以下のような感じです。

  • Region
    • 1つの連続したメモリを用意し、要求に対してはメモリ割り当て、破棄は何もしない、というAllocator
    • 用意したメモリを使い切ると単に割り当て失敗となり、nullが返る
    • 言うまでもなく単純で高速、動作もわかりやすいがメモリを使いまわさないので無駄が多い
  • BitmappedBlock
    • ブロックサイズを指定して連続なブロックを(複数)準備しておき単純なヒープを構成するAllocator
    • 古典的だがチューニングしやすい、初歩的なGCのバックエンドのようなもの
    • 割り当てと破棄を繰り返すとどうしても断片化が起こる問題がある
  • GCAllocator
    • D言語のGCをバックエンドとして動作するAllocator
  • MAllocator
    • C言語のヒープ操作(malloc/free)をバックエンドとして動作するAllocator

これらに加え、いくつかのラッパーとなる特殊なAllocatorが用意されています。

たとえば、サイズの閾値を指定して小さいオブジェクトと大きなオブジェクトをそれぞれ専用のAllocatorで管理する機能を持った Segregator などです。
小さいオブジェクトで効率的なAllocatorと大きいオブジェクトが得意なAllocatorを使い分ければ当然効率も上がろうというもので、そういった目的で使用するケースが多いかと思います。（そう単純ではないことも多いですが）

問題その１

ここから今回新しいAllocatorの開発動機になります。

メモリの再利用は安全ではない

細かい話は後述しますが、メモリの再利用で何が危険かというと、ちょっと気を抜くと脆弱性につながる可能性があるということです。

たとえば以下のような順序で処理されたとき脆弱性につながる可能性があります。

  1. オブジェクトを一度割り当てた後に破棄
  2. 1のメモリを再利用して別のオブジェクトを作る
  3. 2で初期化忘れやバッファオーバーランがあると1のオブジェクトデータを読み取ってしまう（かもしれない）

細かく言えば色々なパターンがありますが、無関係のデータを別の処理に使ってしまう、という可能性があり、何か嫌な予感がしますよね？
まぁ悪いのは初期化忘れ等なので、これをあまり言っても仕方ないところはあります。

この問題は非常に根本的なもので、Allocatorを作る際は常にこういったことを考える必要がある、というのが今回の大きな制約となります。

また実際のところ、このあたりはD言語の各種既定の動作の理由だったりします。
GCを使って、変数初期化して、境界チェックをちゃんとする、というのが上記の対策になっており、多少効率を犠牲にしても生産性向上に寄与しています。

解決策

さて、非常に根本的な問題とか言いましたが、この問題の解決策は実はとてもシンプルです。

ずばり、割り当てのたびにアドレスを増やしていき再割り当てをしない、という戦略です。

メモリを使いまわさないということで嫌な予感もしますが、小さいプログラムであればほとんど問題もなく意外に優秀な戦略です。本当に64bit環境は偉大です。メモリ16GBは人権です。

スライドに Ascending Page Allocator とありますが、この戦略を取るAllocatorが std.experimental.allocatorのBuildingBlockにそのままAscendingPageAllocator という名前で用意されています。

SafeAllocator v1.0

というわけで、この戦略をSafeAllocatorのv1.0とします。

ただまぁ見るからに大変効率が悪いので、実際はちょっと改造して以下のようにします。

  • メモリを16byte毎に「ページ」という単位で扱う
  • 更にページを束ねてAlignを2MB単位でそろえた「ブロック」で管理する
    • 確保しっぱなしだとさすがに気まずいので、利用されないブロックは破棄するようにする
    • 確保と破棄を効率化したいので、ある程度まとまった単位で扱うようにする
  • さらにオブジェクトサイズ毎にブロックを分ける
    • オブジェクトサイズでブロックを分けると、サイズに比例してページサイズも大きくして良いため、使用状況を管理するBitmapが減らせて色々効率化できる

ブロックを分けるあたりやや小手先の要素ですが、こうするとだいぶ断片化がマシになる傾向があるそうです。

なお、標準ライブラリにはAlignをそろえるためのBuildingBlockも用意されており、AlignedBlockListというものが使えます。
これを標準のSegregatorとAscendingPageAllocatorと組み合わせると以下のコードになります。スライドからの抜粋です。

SafeAllocator_v1.0
alias SafeAllocator = Segregator!(
    16, AlignedBlockList!(SafeBitmappedBlock!16, AscendingPageAllocator*, 1 << 21),
    32, AlignedBlockList!(SafeBitmappedBlock!32, AscendingPageAllocator*, 1 << 21),
    64, AlignedBlockList!(SafeBitmappedBlock!64, AscendingPageAllocator*, 1 << 21),
    128, AlignedBlockList!(SafeBitmappedBlock!128, AscendingPageAllocator*, 1 << 21),
    ..., // 扱うオブジェクトやブロックサイズを考えて必要なだけ用意する
    AscendingPageAllocator*
);

まぁぶっちゃけ初見だと意味わかりませんでしたが、これ自体理解できてなくてもコンセプトがなんとなく分かれば問題ないと思います。

問題その２

メモリの断片化がひどい

ここまでやってもメモリは再利用されないため、割り当てと破棄が繰り返されるたびに断片化がひどくなっていきます。
破棄されたところは空き領域なのに要求があればOSからメモリを取ってきてしまう、という状況なので、小さいプログラム向けには良いかもしれませんが、まだちょっと日常使いは難しい感じです。

安全性制約

メモリが再利用したい！ということですが、その前にどうすれば安全に使いまわせるか？を考えます。

脆弱性のよくある1つのパターンとして、

  1. ある型を割り当て、ユーザー入力値を受け付ける
  2. そのオブジェクトが破棄される
  3. 破棄されたメモリが別の型に再割り当てされる
  4. それをもとに何か処理が行われるとき、初期化を忘れるとユーザー入力値を使ってしまう

という状況があります。

最初の問題で例示された状況の具体例ですが、バッファオーバーフロー/オーバーランがなくとも、初期化忘れだけでユーザー入力値を読み取ってしまう、という点が問題です。だいぶ敷居が下がってしまった気がします。

メモリの再利用というのは言ってしまえば、持っているフィールドが違うオブジェクトにキャストしたような状態なわけですが、実際これが起きてもAllocatorの中なので、なかなか気づけないんじゃないでしょうか？

というわけで、次はこれを回避しつつメモリを再利用するのが目標です。

解決策

さて、ずばりどうするかというと、同じ型でのみメモリを再利用するという戦略を取ると大体解決します。
具体的には扱う型毎にAllocatorを分けてしまうという方法です。いわゆる「ObjectPool」というやつですね。

なんといっても「再利用しても元々同じ型」なので、「意図しない用途に使われることはないだろう」というわけです。

念のため補足しておくと、実際のところアプリ内でメモリを頻繁に割り当てたり破棄したりする型はそう多くないというのが経験的に知られています。
ObjectPoolの利用例としてよく挙げられるのも弾幕シューティングゲームの弾オブジェクトなどですし、何となくわかる気はします。

つまり、実際にAllocatorで管理しなければいけない型はそこまで多くないので、Allocatorをたくさん用意する必要はないだろう、その辺の課題はきっと無視して大丈夫、ということです。

（ぶっちゃけこの辺で考えるのやめてGCに戻りたくなってきます）

SafeAllocator v2.0

というわけで、これをSafeAllocatorのv2.0とします。

これはすでに使ったAlignedBlockListとBitmappedBlockとAscendingPageAllocatorで作れます。
スライドからの抜粋ですが、以下のようになります。

SafeAllocator_v2.0
struct SafeAllocator(T)
{
    // 効率のため必要なサイズを2^Nに切り上げてブロックサイズとする
    alias blockSize = roundUpToPowerOf2(stateSize!T);
    alias AllocType = AlignedBlockList!(
        BitmappedBlock!blockSize,
        AscendingPageAllocator*,
        1 << 21
    );

    // Allocatorのインターフェースを実装
}

// 型毎にAllocatorを初期化して返す関数
SafeAllocator* getSafeAllocator(T)()
{
    static SafeAllocator!T safeAllocator;
    if (!safeAllocator.isInit()) {
        safeAllocator.initialize();
    }
    return &safeAllocator;
}

// 使用例
Point* p = getSafeAllocator!Point().make!Point();
getSafeAllocator!Point().dispose(p);

User* u = getSafeAllocator!User().make!User();

はい。これでメモリが再利用可能になります。まぁこれもAllocator周りの組み合わせ方は初見だと結構読み解くのが難しいです。
とにかく、型毎に別のAllocatorになった雰囲気が伝われば大丈夫です。

実際ObjectPoolとして実用されている方法で、実用レベルです。一体これ以上何を求めるというのか。

しかし、これはまだ最終形態ではありません…（ここでフリーザ様挿絵）（あれ？スライドのこれもう最終形態じゃない？）

問題その３

型が多いとやっぱり断片化する

さて、すでにほぼ実用レベルではありますが、まだ課題はあります。

今回の状況は、Allocatorは「ブロック」という単位である程度まとめてメモリを確保する。しかしすべてのAllocatorがきっちりメモリを使い切るとは限らない、というのが問題です。

するとどうなるかというと、メモリが詰まった領域の最後に未使用領域がくっついている、それがたくさんある、つまり未使用領域があちこちにたくさんある、という状況になります。こういう断片化もあります。

この未使用領域が無くせれば良いのですが、現実問題としてかなり困難を極めそうです。

そんなことできるなら最初からやっている！という話ですが、冷静に考えても使用量をあらかじめ見積もって上限を決めるような方法しかないかと思います。
組み込みなら当然やることかと思いますが、いずれにしてもアプリケーションの要件次第ですし、おそらく決められない場合のほうが多いでしょう。

となると、一般的な攻め方としてはAllocatorの数を減らすという方向性になってきます。Allocator、どうやったら減らせるでしょうか？

解決法

と、ここまでが長い前置きでした。ここからが今回の本題です。

基本方針

スライドの抜粋ですが、ものすごく素朴な話から入ります。

名前と年齢を持つ User構造体、IDと値段を持つStock構造体が例として挙げられています。
要するに以下の2つです。型の善し悪しは置いといて、これだけで何が言いたいか大体わかると思います。

struct User
{
    char[] name;
    int age;
}

struct Stock
{
    char[] id;
    int price;
}

...

...

...

はい、フィールドを見ると全く同じ型です。しかし名前が違うので別の型として扱われます。

ObjectPoolの考え方でいくと、それぞれにAllocatorを用意する必要があるため確保する領域も2倍、未使用領域も2倍、それぞれ別の場所、ということになります。

これらを1つのAllocatorで扱えるようになれば、バッファオーバーラン的な問題は起こさないままAllocatorを共有できます。

型の名前なんて飾りだったのだ。

これらをまとめるために Layout という考え方を導入してAllocatorを1つで済むようにします。

型のレイアウト

実際どのような情報をもとに同じレイアウトだと言えば良いでしょうか？

発表者のAlexandruさんが考えたのは以下のようなものです。

struct Point
{
    int x;
    int y;
}

// xのoffset、xの型、yのoffset、yの型、型のサイズ
Layout!Point = [0, int, 8, int, 16]

struct User
{
    char[] name;
    int age;
}

// nameのoffset、nameの型、ageのoffset、ageの型、型のサイズ
Layout!User = [0, char[], 16, int, 24]

はい。使うのは以下の2つです。

  • フィールド毎のオフセットと型
  • オブジェクトの全体サイズ

前者は当然必要ですが、後者はalign調整の結果で変わってくる部分なので、ここも情報として持ちます。

記述は配列のように見えますが、これは疑似コードで実際はそういう情報を持った型だと思ってください。あくまで静的に決定できる範囲の情報です。

さて、この情報をもとにAllocatorを分ければ、前述の脆弱性であった問題は回避しつつAllocatorを共有できそうです。
別の型と言ってもフィールドは同じわけですから、前述のバッファオーバーランの類は起こりません。
ただしフィールドの用途は違う場合があるので、厳密には共有して大丈夫か一度考えたほうが良いです。

SafeAllocator v3.0

これをもとにAllocatorを書くと以下のようになります。

SafeAllocator_v3.0
struct SafeAllocator(T)
{
    alias blockSize = roundUpToPowerOf2(Layout!T[$ - 1]); // Layoutからサイズがわかるのでそれを使う
    alias AllocType = AlignedBlockList!(
        BitmappedBlock!blockSize,
        AscendingPageAllocator*,
        1 << 21
    );

    // Allocatorのインターフェースを実装
}

SafeAllocator* getSafeAllocator(T)()
{
    static SafeAllocator!(Layout!T) safeAllocator; // ここでLayout毎にまとめる
    if (!safeAllocator.isInit()) {
        safeAllocator.initialize();
    }
    return &safeAllocator;
}

ちょっと変えただけですね。

Layoutの実装は？

ちょっと残念なところですが、発表の中ではLayoutテンプレートの実装が出てきません。
それらしきリポジトリも見当たらないので、ちょっと作ってみましょう。

方針としては、フィールド列挙してメンバーの型とオフセットが分かればTupleに詰めるだけです。

まず、使いそうな機能としては以下のあたりでしょうか。

  • __traits(allMembers, T)
    • フィールド名を列挙する機能
    • foreachで普通に回せる
  • __traits(getMember, obj, "name")
    • オブジェクトから文字列でメンバーを得る
    • 通常あまり使わないが、メタプログラミングだとたまに使う
    • 静的に解決されるのでjsみたいな真似はできない
  • .offsetofプロパティ
    • フィールドのオフセットを得る
    • 文脈依存プロパティとでも言うのか、構造体のプロパティを取得するときだけ使える
  • .sizeofプロパティ
    • 型のサイズを得る
  • いくつかの情報をまとめるためにテンプレートの可変長引数を通してTuple型を作る
    • 実際には利便性のためstd.metaからAliasSeqをインポートして使う

実装

で、Layoutを求める部分だけですが、私が書いたコードが以下の通りです。
static foreachとかバリバリかと思ってましたが、staticMapを思い出して適用したらいくつかのワンライナーをまとめるだけでした。

import std.meta;

alias Layout(T) = AliasSeq!(staticMap!(GetMemberInfo!T, __traits(allMembers, T)), T.sizeof);

alias GetMemberType(T, string name) = typeof(__traits(getMember, T.init, name));

enum GetMemberOffset(T, string name) = __traits(getMember, T.init, name).offsetof;

template GetMemberInfo(T)
{
    alias GetMemberInfo(string name) = AliasSeq!(
        GetMemberOffset!(T, name),
        GetMemberType!(T, name)
    );
}

実際に使ってみると以下のような情報が取れます。
実用上の都合で対象は構造体しか考えていませんが、align含めて正しい情報が取れていそうです。

struct User
{
    string name;
    int age;
}

align(16) struct User2
{
    string name;
    int age;
}

void main()
{
    pragma(msg, Layout!User);  // tuple(0u, (string), 8u, (int), 12u)
    pragma(msg, Layout!User2); // tuple(0u, (string), 8u, (int), 16u)
}

性能

さて、注目の性能ですが、スライドの図を見てもらえればと思います。

ベンチマークは取ってる最中とのことで、実際のアプリケーションに組み込んでもらうところが課題のようですが、分かっている傾向として以下のようなものがあります。

  • 16bytesほどの小さいオブジェクトであれば、単純に malloc(Mallocator) のほうが速い
  • 64bytesほどのオブジェクトであれば
    • 単一オブジェクトの割り当ては malloc のほうが速い
    • 配列の複数割り当ては SafeAllocator のほうが速い
  • 512bytesほどの大きなオブジェクトであれば総じて SafeAllocator のほうが速い

大きいオブジェクトで同じレイアウトになることは稀かもしれませんが、ObjectPoolで高速化しようとする規模だとベクトル型とか持ってたりして似たレイアウトだったりしないでしょうか。フィールド並び替えるだけで同じになったりするとか、一考の余地があるんじゃないかと思います。

また実際断片化率の調査も並行して実施していくそうです。どうやって調査するのか見当もつきませんが…

まとめ

Allocatorにまつわる脆弱性の問題を取り上げつつ、安全なAllocatorを作りつつ性能を上げていく、というテーマの発表でした。

今後は仕様をもう少し練ったりする必要があるらしいですが、レイアウトベースという考え方はやや珍しい手法かと思いますので今回紹介してみました。
今後標準ライブラリに取り込まれるようであれば、折を見て使っていきたいと思います。

ちなみに、「そもそもAllocator使う機能見当たらないんやけど」という方は、コンテナ周りでAllocatorを色々差し替えられる emsi_containers というパッケージがdubに登録されているので、こちら試してみてください。
UnrolledListなどやや珍しいコンテナもあるので、あなたをチューニング沼に引きずり込んでくれることでしょう。

12
5
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
12
5