newbieからバイナリアンへ

newbieからバイナリアンへ

人参の秘めたる甘さに気づいた大学生日記

【LCR 1.0】LibcCodeReading: malloc編[1]=読み始め・tcache

 

0: 参考

code.woboq.org

 

1: イントロ

libcとかkernelのコードを読もう読もうとは思っていたが

なんやかんやで通して読むのは避けてきた

だがそろそろmallocのコードくらいは呼んでおかないとpwnもきつくなってきた

 

というわけで

glibc mallocソースコードを通読していき

その過程をメモしていく

形式としては全て読み終わった後の総括・まとめではなく

最初から読む進めていく際の通時的な記録である

 

newbieなので誤りがある可能性は大であることは念頭に

 

 

 

 

2: malloc実体の場所

まずmalloc()の宣言の部分

 

strong_alias (__libc_malloc, __malloc) strong_alias (__libc_malloc, malloc)

 

libcのソースを読むのに躊躇してきた理由の一つが

こうしたdefineの多さだったりする

まぁ定義に即して展開すると以下のようになる

 

extern __typeof (__libc_malloc) __malloc __attribute__ ((alias (""__libc_malloc""))) ;

__libc_mallocと同じ型の関数を__libc_mallocaliasとしてmallocいう名で定義している

 

ところでmalloc()を呼んだとき実際にはとこに飛ぶかというと

__GI___libc_malloc (bytes=0x40) at malloc.c:3028
3028	{
gdb-peda$ 

__GI__libc_mallocに飛ぶようだ

 

だがwoboqと手元のglibcを読んでみても__GI___libc_mallocは見当たらない

どうやらglibcは以下の部分でprefixとして__GI_をつけるようだ

#  define hidden_proto(name, attrs...) \
  __hidden_proto (name, , __GI_##name, ##attrs)

よって実体は__libc_mallocであり以下これを読んでいく




3: __libc_malloc【1】tcacheの処理

void *
__libc_malloc (size_t bytes)
{
  void *(*hook) (size_t, const void *)
    = atomic_forced_read (__malloc_hook);
  if (__builtin_expect (hook != NULL, 0))
    return (*hook)(bytes, RETURN_ADDRESS (0));

malloc_hookにエントリがあればそれを実行して終了する

入っていないと想定して以下へ

 

 

#if USE_TCACHE
  /* int_free also calls request2size, be careful to not pad twice.  */
  size_t tbytes;
  checked_request2size (bytes, tbytes);
  size_t tc_idx = csize2tidx (tbytes);
  MAYBE_INIT_TCACHE ();
  DIAG_PUSH_NEEDS_COMMENT;
  if (tc_idx < mp_.tcache_bins
      /*&& tc_idx < TCACHE_MAX_BINS*/ /* to appease gcc */
      && tcache
      && tcache->entries[tc_idx] != NULL)
    {
      return tcache_get (tc_idx);
    }
  DIAG_POP_NEEDS_COMMENT;
#endif

tcacheを使用する場合の処理である

 

checked_request2size()でユーザ指定のサイズをシステム用のサイズに変更する

#define checked_request2size(req, sz) \
({                                    \
  (sz) = request2size (req);            \
  if (((sz) < (req))                    \
      || REQUEST_OUT_OF_RANGE (sz)) \
    {                                    \
      __set_errno (ENOMEM);            \
      return 0;                            \
    }                                    \
})

define内部ではrequest2size macroによって得たszが

オーバーフローを起こしていないか(ユーザ指定サイズより小さくないか)と

最大サイズを超えていないかをチェックしている

#define request2size(req)                                         \
  (((req) + SIZE_SZ + MALLOC_ALIGN_MASK < MINSIZE)  ?             \
   MINSIZE :                                                      \
   ((req) + SIZE_SZ + MALLOC_ALIGN_MASK) & ~MALLOC_ALIGN_MASK)

request2size macroでは上の計算をする

SIZE_SZはsize_tであり、min(ユーザ指定サイズにsize_t分足してalignmentした値, MINSIZE)を返す

こうしてtbytesには実際に取得するサイズが格納される

 

tsize2tidx macroではreqがtcacheの何番目のbinに対応するかのindexを返す

 

MAYBE_INIT_TCACHE macroは以下の通り

# define MAYBE_INIT_TCACHE() \
  if (__glibc_unlikely (tcache == NULL)) \
    tcache_init();
# define __glibc_unlikely(cond)        __builtin_expect ((cond), 0)
# define __builtin_expect(expr, val)   (expr)

なんでこれをマクロにしているかは足りない頭ではよくわからない

単純に if(tcache == NULL) と同じらしい

 

tcacheがNULLならば以下のtcache_init()を行う

tcache_init(void)
{
  mstate ar_ptr;
  void *victim = 0;
  const size_t bytes = sizeof (tcache_perthread_struct);
  if (tcache_shutting_down)
    return;
  arena_get (ar_ptr, bytes);
  victim = _int_malloc (ar_ptr, bytes);
  if (!victim && ar_ptr != NULL)
    {
      ar_ptr = arena_get_retry (ar_ptr, bytes);
      victim = _int_malloc (ar_ptr, bytes);
    }

arena_getはar_ptrをthread_arenaを指すようにしてarena_lock()でロックをしようとするマクロ

arenaを取得したらそのarenaからtcache_perthread_struct分だけ_int_malloc()でchunkを取得する

 

以上の操作に失敗したら、arenaの双方向連結リストを辿り取得できるarenaを探して同様の処理を繰り返す

  if (ar_ptr != NULL)
    __libc_lock_unlock (ar_ptr->mutex);
  if (victim)
    {
      tcache = (tcache_perthread_struct *) victim;
      memset (tcache, 0, sizeof (tcache_perthread_struct));
    }
}

成功したらunlockしtcacheをゼロ初期化してtcache_init()終了

 

なおtcacheとして確保されるtcache_perthread_structは以下の構造体

typedef struct tcache_perthread_struct
{
  char counts[TCACHE_MAX_BINS];
  tcache_entry *entries[TCACHE_MAX_BINS];
} tcache_perthread_struct;
typedef struct tcache_entry
{
  struct tcache_entry *next;
  /* This field exists to detect double frees.  */
  struct tcache_perthread_struct *key;
} tcache_entry;

各サイズのbinに何個chunkが入っているかを数えるcounts

実際のbinを表すentriesで構成されている

entriesには次のchunkを指すnext、コメント曰くdouble freeを検知するためのkeyメンバがある

keyメンバの用法についてはこの先出てきたときまで取っておく



__libc_malloc()に戻る

  DIAG_PUSH_NEEDS_COMMENT;
  if (tc_idx < mp_.tcache_bins
      /*&& tc_idx < TCACHE_MAX_BINS*/ /* to appease gcc */
      && tcache
      && tcache->entries[tc_idx] != NULL)
    {
      return tcache_get (tc_idx);
    }
  DIAG_POP_NEEDS_COMMENT;
#endif

_mpmalloc parameter のことであり以下で定義されている

/* There is only one instance of the malloc parameters.  */
static struct malloc_par mp_ =
{
  .top_pad = DEFAULT_TOP_PAD,
  .n_mmaps_max = DEFAULT_MMAP_MAX,
  .mmap_threshold = DEFAULT_MMAP_THRESHOLD,
  .trim_threshold = DEFAULT_TRIM_THRESHOLD,
#define NARENAS_FROM_NCORES(n) ((n) * (sizeof (long) == 4 ? 2 : 8))
  .arena_test = NARENAS_FROM_NCORES (1)
#if USE_TCACHE
  ,
  .tcache_count = TCACHE_FILL_COUNT,
  .tcache_bins = TCACHE_MAX_BINS,
  .tcache_max_bytes = tidx2usize (TCACHE_MAX_BINS-1),
  .tcache_unsorted_limit = 0 /* No limit.  */
#endif
};

この記法はC99に特有であり、型を宣言せずに構造体を定義できる

見た感じ+コメント曰く本当にただのパラメタ群であるようだ

 

このパラメタの内、tcacheの最大bin数を使ってインデックスが正当かを検討し

また、該当するインデックスのbinにchunkが存在するかを確認している

tcacheに該当するchunkがあればget_tcache()でchunkを取得し__libc_malloc()は終了となる

 

static __always_inline void *
tcache_get (size_t tc_idx)
{
  tcache_entry *e = tcache->entries[tc_idx];
  assert (tc_idx < TCACHE_MAX_BINS);
  assert (tcache->counts[tc_idx] > 0);
  tcache->entries[tc_idx] = e->next;
  --(tcache->counts[tc_idx]);
  e->key = NULL;
  return (void *) e;
}

tcache_get()の中身はこれだけ

binの根本にあるchunkをリストから外して返している

チェック機構は以下のもの

tc_idxがTCACHE_MAX_BINS未満である

(但しこのチェックは呼び出し元でも行っているため冗長な気がする。。。)

tcache->counts[tc_idx]がNULLでない

(このチェックがあるということはcountsと実際のchunkの個数が合わなくなることがあり得るということだろうか。。。)

獲得されるchunkのkeyをNULLクリア

(ここまでで察するにkeyはchunkに繋がれていないときはNULLになるらしい)

 

予め知っていたとおりchunkのsizeの確認等は一切行われておらず

要求サイズのbinに繋がってさえいれば獲得することができるようになっている

 

以上でtcacheの初期化及びtcacheからのchunk獲得の一切は終了である




4: __libc_malloc【2】tcache以降の処理(_int_malloc()を除く)

tcacheを使わない際の処理は以下のように続く

  if (SINGLE_THREAD_P)
    {
      victim = _int_malloc (&main_arena, bytes);
      assert (!victim || chunk_is_mmapped (mem2chunk (victim)) ||
              &main_arena == arena_for_chunk (mem2chunk (victim)));
      return victim;
    }

 

//glibc/sysdeps/unix/sysv/linux/sysdep-cancel.h
#  define SINGLE_THREAD_P \
  __glibc_likely (__libc_multiple_threads == 0)
// glibc/misc/sys/cdefs.h
# define __glibc_likely(cond)        __builtin_expect ((cond), 1)

なお後者のdefineは#if __GNUC__ >= 3で囲まれているが

__GNUC__は4とdefineされているため常に上の定義である

相変わらずこのマクロはよくわからないが、まあそのまま引数の条件式が評価されることになる

つまりSINGLE_THREAD_P__libc_multiplethreads==0ならば真でありシングルスレッドであることを示す

シングルスレッドである場合にはわざわざarenaのgetをせずに_int_malloc()を呼ぶそうだ

 

その後に出てくる3つのマクロchunk_is_mmappedmem2chunkarena_for_chunk

 

#define chunk_is_mmapped(p) ((p)->mchunk_size & IS_MMAPPED)

IS_MMAPPEDフラグが立ってるか調べる

#define mem2chunk(mem) ((mchunkptr)((char*)(mem) - 2*SIZE_SZ))

↑chunkのユーザスペースからmalloc側が使うアドレスへの変換

#define arena_for_chunk(ptr) \
  (chunk_main_arena (ptr) ? &main_arena : heap_for_ptr (ptr)->ar_ptr)
//そのchunkがmain_arena以外から取ってきたものかチェック
#define chunk_main_arena(p) (((p)->mchunk_size & NON_MAIN_ARENA) == 0)

↑arena_for_chunkは文字通りそのchunkが属するarenaのアドレスを返す

 

つまりif branchでは

・chunkの割当自体に成功していること

・mmappedされていないこと(なんで?)

・main_arenaから取得されていること(シングルスレッド想定なので)

を検証しており、全てを満たしていればシングルスレッドでのメモリ割り当ては終了し返る

 

以下はマルチスレッドの場合の割当処理

 

arena_get (ar_ptr, bytes);
  victim = _int_malloc (ar_ptr, bytes);
  /* Retry with another arena only if we were able to find a usable arena
     before.  */
  if (!victim && ar_ptr != NULL)
    {
      LIBC_PROBE (memory_malloc_retry, 1, bytes);
      ar_ptr = arena_get_retry (ar_ptr, bytes);
      victim = _int_malloc (ar_ptr, bytes);
    }
  if (ar_ptr != NULL)
    __libc_lock_unlock (ar_ptr->mutex);
  assert (!victim || chunk_is_mmapped (mem2chunk (victim)) ||
          ar_ptr == arena_for_chunk (mem2chunk (victim)));
  return victim;
}

まずは競合しないようarenaをlockし、その後_int_malloc()でvictimにchunkを割り当てる

後の処理は今まで出てきたものとほとんど同じであるため省略




これで__libc_malloc()の内メインとなる_int_malloc()以外は読み終わった

次エントリでは本題の_int_malloc()に入っていく







続く・・・