mmap したファイル向けに malloc を作ってみた

ファイルを mmap した仮想メモリアドレスの上で、データ構造を操作して、そのままファイルに保存したいと思われたことはありませんでしょうか。

実際にやってみようとすると、mmap された仮想メモリ領域の空き空間の管理を自分で行わなければならず、ファイルが mmap された領域からメモリを確保してくれる malloc のような仕組みが必要ということに気づきました。

通常の malloc は内部的に独自で brk のようなシステムコールを実行して、OS からメモリ領域を確保しているので、独自にファイルを mmap した領域についてはメモリ管理をしてくれません。

今回は、通常の malloc と独立して、mmap したファイルの仮想メモリ領域の管理をしてくれる fmalloc という malloc を作りました。

ポイントとして、以前の記事にある fm_ptr という、仮想メモリアドレスとファイル内のオフセットを自動で変換してくれるスマートポインタを使って実装しました。fm_ptr については過去の記事をご参照ください。

これにより、通常のメモリ内部で完結するプログラムを大幅に変更することなく、メモリマップトファイルを経由してファイルへデータ構造の保存ができるようになります。

ソースコードは GitHub で公開しておりますので、ご興味がありましたら是非お試しください。

github.com

malloc に求められること

malloc については以下のような要件があると思われます。

• 速度
• メモリ領域の利用効率
• マルチコアでのスケーラビリティ

例えば、実装によりますが、リストやツリー構造では、新しくノードを追加するごとに、malloc でノード用のメモリを確保します。なので、特にキーバリューストア等のようなプログラムでは、malloc の速度は重要になります。

ですが、上記の要件を達成するのは容易ではなく、独自で新しく実用的な malloc を実装するのはとても難しいです。

mmap したファイル用の malloc の作り方

高速かつ効率の良い malloc を一から作るのはとても難しいので、今回は、広く利用されている ptmalloc という malloc の実装を拡張して、メモリマップトファイルのメモリ領域からメモリ確保を行えるようにしました。

ptmalloc は、Wolfram Gloger さんという方が、Doug Lea さんという方によって実装された dlmalloc と呼ばれる実装を、マルチスレッド環境においてスケールできるように拡張したものです。これは、広く GNU C ライブラリの一部として利用されている malloc の元になっています。

ptmalloc は、比較的新しい jemalloc 等と比べて遅いと言われていますが、一般の人が新しく実装しなおすよりはるかに素晴らしいものであることは間違いありません。

今回は、拡張のしやすさの観点から、ptmalloc を元に、fmalloc という mmap したファイル用の malloc を作ってみました。

fmalloc

fmalloc における、ptmalloc からの変更点は、主に２点です。

一つ目は、ptmalloc が brk 等のシステムコールを利用して、独自にメモリ領域を確保している箇所を変更して、代わりに、ファイルが mmap されているメモリ領域からメモリを確保するようにしました。

二つ目は、ptmalloc が内部の実装に用いている構造体内部のポインタ宣言を fm_ptr に置き換えました。malloc はメモリ領域を小さいチャンクに分けて管理します。通常の malloc の実装では、チャンクへのポインタは仮想メモリアドレスで表現されていますが、そのポインタは、次回 mmap された時にも参照できる必要があるので、ファイルオフセットの値がファイルに書き込まれる必要があります。

今回は、malloc 実装内部での、仮想メモリアドレスとファイルオフセットの変換を自動で行うために、fm_ptr を利用しました。

その結果、コメントアウトを除いて約 4000 行ほどある ptmalloc 実装のうち、150 行程度の変更で、実装をメモリマップトファイル用に適用できました。その他、API の実装がだいたい追加で合計 250 行程度になりました。

fm_ptr のおかげで、ポインタを全箇所について手作業で変換しなくてよかったので、だいぶ実装の負担が軽減されたと思っています。

API

複数のメモリマップトファイルを扱えるように、fm_info という構造体に対して、一つのファイルをひも付けるようにしました。

以下の関数で、fm_info 構造体を、filepath で指定されたファイルに対してひも付けます。この関数は内部的に mmap を実行します。

struct fm_info *fmalloc_init(const char *filepath, bool *init)

次に、現在、どのメモリマップトファイルに対して作業を行っているかを設定するための以下の関数を実行します。これはおまじないのようなものです。

void fmalloc_set_target(struct fm_info *fi)

以上が、通常の malloc と大きく異なる点です。残りの API は以下の２つで、fmalloc は、malloc と、ffree は free と対応した挙動をし、唯一の異なる点として、メモリの確保と解放を fmalloc_set_target で設定したメモリマップトファイルの仮想メモリ領域の上から行うという点です。

void *fmalloc(size_t size)
void ffree(void *addr)

ファイル上のデータの配置

永続ストレージを扱うプログラムの特徴として、データ構造の開始位置をスーパーブロックのような決まった場所に置いておくということがあります。

fmalloc では、以下のようにデータを配置します。

 0             4KB           8KB                 end
 |-- fm_super --|-- for app --|-- ... malloc ...--|

最初の４KBは、fmalloc 独自のデータを置いておきます。

４KBから８KBまでは、アプリケーションのために開けておきます。ここにアプリケーションは、例えば連結リストであれば、連結リストの先頭のノードを配置したりできます。

８KB以降の領域は fmalloc によって管理されます。

実際のプログラム

以下が、実際に fmalloc を適用した連結リストの実装例です。以下のプログラムは、fmalloc のレポジトリにサンプルプログラムとして含まれています。

以下のプログラムを実行すると、一度目の実行で、０から９までの値をもつノードを連結リストに追加し、ファイルに保存します。二度目以降の実行では、ファイルから保存された連結リストを読み出して、０から９までの値を表示します。

#include <fmalloc.hpp>

/* list implementation */
struct node {
  int val;
  fm_ptr<struct node> next;
} __attribute__((packed));

static void list_append(struct node *head, struct node *newnode)
{
  struct node *n = head;
  while (n->next) {
    n = n->next;
  }
  n->next = newnode;
}

/* app reserved super block */
struct app_super {
  fm_ptr<struct node> head;
};

/* example append operation */
static void append_nodes(struct node *head)
{
  int i;
  printf("writing list data...\n");
  for (i = 0; i < 10; i++) {
    struct node *n = (struct node *) fmalloc(sizeof(struct node));
    n->val = i;
    n->next = NULL;
    list_append(head, n);
  }
  printf("done.\n");
}

/* example read operation */
static void read_nodes(struct node *head)
{
  struct node *n = head->next;
  printf("reading list data...\n");
  while (n) {
    printf("%d\n", n->val);
    n = n->next;
  }
  printf("done.\n");
}

int main(int argc, char const* argv[])
{
  struct app_super *super;
  bool init = false;
  struct fm_info *fi;

  if (argc < 2) {
    printf("please specify a data file\n");
    exit(1);
  }

  fi = fmalloc_init(argv[1], &init);
  fmalloc_set_target(fi);

  /* fmalloc reserves 4KB ~ 8KB for app for locating super block */
  super = (struct app_super *) ((unsigned long) fi->mem + PAGE_SIZE);

  if (init) {
    super->head = (struct node *) fmalloc(sizeof(struct node));
    append_nodes(super->head);
  } else {
    if (super->head) {
      read_nodes(super->head);
    }
  }

  return 0;
}

通常の連結リストと異なる点は、主に以下の５点と思われます。

1. ポインタを fm_ptr で宣言する
2. fmalloc_init を実行する
3. fmalloc_set_target を実行する
4. アプリケーション用のスーパーブロックに連結リストの先頭を配置する
5. リストのノード確保のため、malloc の代わりに fmalloc を実行する

このように、fmalloc を使うと、メモリマップトファイルに比較的簡単にデータ構造を保存できるようになります。