Zenn
🐷

malloc.c を読む (arena)

2023/09/14に公開
Linux
#
CTF
#
pwn
tech

malloc() は動的にメモリを確保して free() で開放してくれます。

void *malloc(size_t size);
void free(void *ptr);

このシリーズではこれらの関数が内部でどのように処理されるのかを調べていきます。

今回はアリーナの処理を中心に調べていきます。

シリーズは malloc.c を題材としていますがここでは arena.c を主に読むことになります。

ここで扱う glibc のバージョンは v2.38 です。また glibc のソースコードはブラウザ上で読むことができます。

アリーナとは

プロセスは sbrk() や mmap() システムコールによって OS からメモリプールを獲得します。このメモリプールをアプリケーションに高速に分配する bin と呼ばれる機構があります。bin はメモリプールとは別にメモリプールの管理部で管理されています。そしてメモリプールとその管理部を合わせてアリーナ (arena) と呼びます。

アリーナの管理部は malloc_state 構造体に書かれてあります。初期状態ではヒープ領域にサイズゼロのメモリプールとグローバル領域に main_arena と呼ばれる管理部があります。

struct malloc_state
{
  __libc_lock_define (, mutex);     // arena へのアクセスを serialize する
  int flags;                        // ヒープメモリが連続であるか

  int have_fastchunks;              // fastbins が空ではないことを表す真偽値
  mfastbinptr fastbinsY[NFASTBINS]; // fastbins の先頭チャンクへのポインタ

  mchunkptr top;                    // ヒープ領域の最後にある未使用の大きなチャンク
  mchunkptr last_remainder;         // 分割して確保した際に余った領域の最新のチャンク

  mchunkptr bins[NBINS * 2 - 2];    // unsortedbin smallbins largebins の先頭・末尾
  unsigned int binmap[BINMAPSIZE];  // これらを素早く見つける為に使われるビットベクタ

  struct malloc_state *next;        // arena の単方向リスト
  struct malloc_state *next_free;   // 使われていない arena の単方向リスト
  INTERNAL_SIZE_T attached_threads; // arena にアクセスしているスレッドの数

  INTERNAL_SIZE_T system_mem;       // arena によって現在確保されているメモリの合計値
  INTERNAL_SIZE_T max_system_mem;   // system_mem の最大値
};

static struct malloc_state main_arena =
{
  .mutex = _LIBC_LOCK_INITIALIZER,
  .next = &main_arena,
  .attached_threads = 1
};

各フィールドに関連する処理

flags

アリーナの状態に関するフラグです。使うビットは NONCONTIGUOS_BIT == 2 の 1 つだけだと思います。これは MORECORE したときに連続した領域を返すことを保証しないことを表すフラグです。フラグがクリアされているときは連続性をとことん利用して top chunk を大きくします。初期値は MORECORE_CONTIGUOUS から書き込まれ、mmap で拡張するとフラグが立ちます。

ちなみにこのフィールドは前に max_fast として、各アリーナにおける fastbins が扱うチャンクサイズのパラメータに使われていました。

top

top chunk とは最上位つまり終端に置かれた特別なチャンクでどの bin にも含まれていません。

これは malloc() では他に割り当てられるチャンクがない場合にのみ切り出され、top chunk が肥大化した場合は free() 時に自動的に OS に返されます。top chunk は最初 initiali_top と呼ばれるサイズがゼロの bin を指しているので malloc() を呼ぶことで sbrk() が呼ばれてヒープ領域が拡張され、top chunk も拡張されます。

/* Conveniently, the unsorted bin can be used as dummy top on first call */
#define initial_top(M)              (unsorted_chunks (M))

static void
malloc_init_state (mstate av)
{
  int i;
  mbinptr bin;

  /* Establish circular links for normal bins */
  for (i = 1; i < NBINS; ++i)
    {
      bin = bin_at (av, i);
      bin->fd = bin->bk = bin;
    }

#if MORECORE_CONTIGUOUS
  if (av != &main_arena)
#endif
  set_noncontiguous (av);
  if (av == &main_arena)
    set_max_fast (DEFAULT_MXFAST);
  atomic_store_relaxed (&av->have_fastchunks, false);

  av->top = initial_top (av);
}

last_remainder

smallbins / largebins / last_remainder においてチャンクの分割を行ったときの残りのチャンク (remainder) を unsortedbin に入れるのと同時に last_remainder に格納することで参照局所性を活かします。ただし残りが smallbins の大きさとなったチャンクしか扱いません。

マルチスレッド

アリーナは mutex を用いてロックし、複数のスレッドがメモリプールを共有することができます。

ただし、あるスレッドがチャンクを確保しようとしたときに main_arena がロックされていた場合、mmap() で新たなヒープ領域を作ります。この為、最終的にヒープ領域の数はスレッド数くらいに落ち着きます。

mmap() で得られたヒープ領域では先頭に管理情報の実体 heap_info と管理部の実体 malloc_state を置き、各ヒープ領域は malloc_state.next _heap_info.prev によって双方向リストが作られます。そしてスレッドが終了したときには next_free に繋がれます。ちなみに main_arena では heap_info に相当するものはありません。

typedef struct _heap_info
{
  mstate ar_ptr;            // このヒープ領域のアリーナへのポインタ
  struct _heap_info *prev;  // 前のヒープ領域
  size_t size;              // アリーナのバイト数
  size_t mprotect_size;     // PROT_READ|PROT_WRITE で mprotect されたバイト数
  size_t pagesize;          // ページサイズ
  char pad[-3 * SIZE_SZ & MALLOC_ALIGN_MASK]; // メモリ境界を揃える為のパディング
} heap_info;

また mmap() で得られたヒープ領域は 1MB でアラインされているため、どんなチャンクのアドレスでも先頭 5 nibbles をクリアすることで _heap_info malloc_state を見つけてアリーナの管理部にアクセスできます。ちなみに main_arena のチャンクはそれは出来ず、直接アクセスする他ありません。チャンクにこの違いを教える為にチャンクには NON_MAIN_ARENA というフラグがあるという訳です。

アリーナのパラメータ

アリーナに関するパラメータは malloc_par 構造体に書かれてあります。glibc を書き換えてビルドしたものをリンクすることでパラメータをチューニングすることもできます。

struct malloc_par
{
  /* Tunable parameters */
  unsigned long trim_threshold;   // trim する閾値
  INTERNAL_SIZE_T top_pad;        // アリーナを拡張するときのサイズ算出に使用
  INTERNAL_SIZE_T mmap_threshold; // 既にある領域を使わず mmap munmap を用いて管理するサイズの閾値
  INTERNAL_SIZE_T arena_test;
  INTERNAL_SIZE_T arena_max;

  INTERNAL_SIZE_T thp_pagesize;   // Transparent Huge Page のページサイズ
  INTERNAL_SIZE_T hp_pagesize;    // 通常のページサイズで mmap はこれに align される
  int hp_flags;

  int n_mmaps;                    // mmap した回数
  int n_mmaps_max;                // mmap できる上限
  int max_n_mmaps;                // これまでの n_mmaps の最大値
  int no_dyn_threshold;           // mmap_threshold の設定時に動的な変更をやめる為のフラグ

  INTERNAL_SIZE_T mmapped_mem;    // mmap() で確保した領域サイズの合計
  INTERNAL_SIZE_T max_mmapped_mem; // これまでの mmaped_mem の最大値

  char *sbrk_base;                // ヒープ領域のベースアドレス

  size_t tcache_bins;             // tcache bins の総数
  size_t tcache_max_bytes;        // 最大チャンクサイズ
  size_t tcache_count;            // 各 tcache bin が持てる最大のチャンク数
  size_t tcache_unsorted_limit;   // unsortedbin が持てる最大のチャンク数
};

static struct malloc_par mp_ =
{
  .top_pad = DEFAULT_TOP_PAD,                           // 0
  .n_mmaps_max = DEFAULT_MMAP_MAX,                      // 65536
  .mmap_threshold = DEFAULT_MMAP_THRESHOLD,             // 128 * 1024
  .trim_threshold = DEFAULT_TRIM_THRESHOLD,             // 128 * 1024
#define NARENAS_FROM_NCORES(n) ((n) * (sizeof (long) == 4 ? 2 : 8))
  .arena_test = NARENAS_FROM_NCORES (1),
  .tcache_count = TCACHE_FILL_COUNT,                    // 7
  .tcache_bins = TCACHE_MAX_BINS,                       // 64
  .tcache_max_bytes = tidx2usize (TCACHE_MAX_BINS-1),   // 0x410
  .tcache_unsorted_limit = 0 /* No limit.  */
};

まとめ

チャンクから始まり bins、アリーナまで紹介しました。これで malloc に関しては完璧なんじゃないでしょうか。

これで malloc.c の読書は一旦終わりです。気が向いたら詳細についてや他の malloc 関数についても紹介したいと思います。

Discussion