newbieからバイナリアンへ

newbieからバイナリアンへ

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

【LCR 1.1】LibcCodeReading: malloc編[2]=fastbins・smallbins

 

0: 参考

code.woboq.org

 

1: イントロ

前回に引き続きglibcmallocを読んでいく

今回は本丸である_int_malloc()に入る




2: fastbinsの処理(tcacheとの関連)

_int_mallocglibc/malloc/malloc.cにおいて3527~4440行までを占めている

これを先頭からややアバウトに、且つ通時的に読んでいくこととする

 

なお今回から頻出するarenaはmalloc_state型であり以下に定義される

struct malloc_state
{
  /* Serialize access.  */
  __libc_lock_define (, mutex);
  /* Flags (formerly in max_fast).  */
  int flags;
  /* Set if the fastbin chunks contain recently inserted free blocks.  */
  /* Note this is a bool but not all targets support atomics on booleans.  */
  int have_fastchunks;
  /* Fastbins */
  mfastbinptr fastbinsY[NFASTBINS];
  /* Base of the topmost chunk -- not otherwise kept in a bin */
  mchunkptr top;
  /* The remainder from the most recent split of a small request */
  mchunkptr last_remainder;
  /* Normal bins packed as described above */
  mchunkptr bins[NBINS * 2 - 2];
  /* Bitmap of bins */
  unsigned int binmap[BINMAPSIZE];
  /* Linked list */
  struct malloc_state *next;
  /* Linked list for free arenas.  Access to this field is serialized
     by free_list_lock in arena.c.  */
  struct malloc_state *next_free;
  /* Number of threads attached to this arena.  0 if the arena is on
     the free list.  Access to this field is serialized by
     free_list_lock in arena.c.  */
  INTERNAL_SIZE_T attached_threads;
  /* Memory allocated from the system in this arena.  */
  INTERNAL_SIZE_T system_mem;
  INTERNAL_SIZE_T max_system_mem;
};

 

_int_malloc()は以下のように始まる

_int_malloc (mstate av, size_t bytes)
{
  checked_request2size (bytes, nb);
  
  if (__glibc_unlikely (av == NULL))
    {
      void *p = sysmalloc (nb, av);
      if (p != NULL)
        alloc_perturb (p, bytes);
      return p;
    }

引数はav:main_arena、bytes:要求サイズである

返り値は成功すれば割り当てたchunkのユーザスペースのアドレスになる

なおbytesはこの時点ではユーザの要求そのままのサイズである

 

まずtcacheの時と同様にシステム用のサイズを計算してnbに格納する

その後arenaがNULLであればsysmalloc()で直接メモリを取りに行くようだ

sysmalloc()の内容については一旦飛ばす

その後のalloc_perturb()では、global変数perturb_byteがノンゼロであれば

割り当てられたchunkのユーザスペースを全てperturb_byte^0xffで埋めることになる

だがコメントからするとテスト関数のようで使われないのかもしれない

(経験的にそんな処理はされないため)

 

 

こいつがfastbinsの処理部分の全て

  if ((unsigned long) (nb) <= (unsigned long) (get_max_fast ()))
    {
      idx = fastbin_index (nb);
      mfastbinptr *fb = &fastbin (av, idx);
      mchunkptr pp;
      victim = *fb;
      if (victim != NULL)
        {
          if (SINGLE_THREAD_P)
            *fb = victim->fd;
          else
            REMOVE_FB (fb, pp, victim);
          if (__glibc_likely (victim != NULL))
            {
              size_t victim_idx = fastbin_index (chunksize (victim));
              if (__builtin_expect (victim_idx != idx, 0))
                malloc_printerr ("malloc(): memory corruption (fast)");
              check_remalloced_chunk (av, victim, nb);
#if USE_TCACHE
              /* While we're here, if we see other chunks of the same size,
                 stash them in the tcache.  */
              size_t tc_idx = csize2tidx (nb);
              if (tcache && tc_idx < mp_.tcache_bins)
                {
                  mchunkptr tc_victim;
                  /* While bin not empty and tcache not full, copy chunks.  */
                  while (tcache->counts[tc_idx] < mp_.tcache_count
                         && (tc_victim = *fb) != NULL)
                    {
                      if (SINGLE_THREAD_P)
                        *fb = tc_victim->fd;
                      else
                        {
                          REMOVE_FB (fb, pp, tc_victim);
                          if (__glibc_unlikely (tc_victim == NULL))
                            break;
                        }
                      tcache_put (tc_victim, tc_idx);
                    }
                }
#endif
              void *p = chunk2mem (victim);
              alloc_perturb (p, bytes);
              return p;
            }
        }
    }

nbがfastbinsの最大サイズ以下であればこの処理を行う

 

fastbin_index macroでfastbinsのidxを得る。このマクロは以下の通り

#define fastbin_index(sz) \
  ((((unsigned int) (sz)) >> (SIZE_SZ == 8 ? 4 : 3)) - 2)

64bitではSIZE_SZ==8であるから要求サイズが4bitシフトされる

ただしbinsの最小サイズが0x20であるからこれをインデックスゼロにするため2を引いている

 

続いてfbにfastbinsY[idx]のアドレスを代入している

fbの型はmfastbin_ptr*であり、これはmalloc_chunk型へのポインタとして定義されている

そしてmalloc_chunk型が見慣れた以下の型である

struct malloc_chunk {
  INTERNAL_SIZE_T      mchunk_prev_size;  /* Size of previous chunk (if free).  */
  INTERNAL_SIZE_T      mchunk_size;       /* Size in bytes, including overhead. */
  struct malloc_chunk* fd;         /* double links -- used only if free. */
  struct malloc_chunk* bk;
  /* Only used for large blocks: pointer to next larger size.  */
  struct malloc_chunk* fd_nextsize; /* double links -- used only if free. */
  struct malloc_chunk* bk_nextsize;
};

ココらへんの細かい説明は特に不要

 

とにかくvictimにはidxに対応するfastbinのポインタが代入される

もしこれがNULLであれば対応するfastbinsがないためfastbinsの処理は終わりになる

 

binにchunkが入っている場合はネストの内側に進む

シングルスレッドの場合にはfastbinsY[idx]の先頭がvictimの次を指すようにする

 

この後にfastbinsのチェック機構がある

ここではvictimのsizeから対応するfastbinのインデックスを計算し

このインデックスとそのchunkが入っていたfastbinのインデックスが異なる場合には

"malloc(): memory corruption (fast)"

というエラーを吐く

pwnで注意すべきfastbinsのサイズチェックはここで行われていた

 

 

その後のcheck_remalloced_chunk()はデバッグ用であり何もしていないため無視

 

 

続くifでfastbinsY[idx]にまだchunkがあるかを確認し

ある場合は全てtcacheにつなぎ替える

 

こんな処理あったかなぁと思ったため以下のテストプログラムを作ってみた

//test program for move from fastbins to tcache when malloc()
int main(int argc,char *argv[]){
  void *p[7];
  void *q,*r[3];
  
  //malloc
  for(int ix=0;ix!=7;++ix){
    p[ix] = malloc(0x20); 
  }
  q = malloc(0x20);       
  for(int ix=0;ix!=3;++ix){
    r[ix] = malloc(0x20);
  }
  
  //free
  for(int ix=0;ix!=7;++ix){
    free(p[ix]);            //on tcache
    p[ix] = NULL;
  }
  getc(stdin);
  for(int ix=0;ix!=3;++ix){
    free(r[ix]);            //on fastbinsY[1]
    r[ix] = NULL;
  }
  free(q);                  //on fastbinsY[1]
  getc(stdin);

  //clear tcache
  for(int ix=0;ix!=7;++ix){
    p[ix] = malloc(0x20);
  }
  getc(stdin);

  //now fastbinsY[0] has 4 chunks in it(q->r[2]->r[1]->r[0])

  //let us see if they are moved to fastbins when malloc(0x20) is called
  getc(stdin);
  q = malloc(0x20);


  return 0;
}

このプログラムではtcacheにchunkがなくfastbinsY[1]にchunkが4つある状態でmallocが呼ばれるという状況が作られている

実際にbinsの様子を見ていくと

pwndbg> bins
tcachebins
empty
fastbins
0x20: 0x0
0x30: 0x5555557563a0 —▸ 0x555555756430 —▸ 0x555555756400 —▸ 0x5555557563d0 ◂— 0x0
0x40: 0x0
0x50: 0x0

このようにfastbinsにあったchunkが

tcachebins
0x30 [  3]: 0x5555557563e0 —▸ 0x555555756410 —▸ 0x555555756440 ◂— 0x0
fastbins
0x20: 0x0
0x30: 0x0
0x40: 0x0

tcacheに繋ぎ変えられている

あまり使う機会もないため意識していなかったが

こういう機構があるのだと再認識できた

 

なおtcacheにchunkが移される際にそのfastbinsY[idx]のkeyにはtcacheのアドレスが格納され

double freeを検知できるようにしてある

 

ということでfastbinの残り物をtcacheに移した後

chunk2memでvictimのユーザスペースのアドレスをpに入れて返している

以上でfastbinsのmalloc処理は全て終了である




 

 

3: smallbinsの処理

nbがsmallbinsの範囲内であれば以下の処理を行う

if (in_smallbin_range (nb))
    {
      idx = smallbin_index (nb);
      bin = bin_at (av, idx);
      if ((victim = last (bin)) != bin)
        {
          bck = victim->bk;
          if (__glibc_unlikely (bck->fd != victim))
            malloc_printerr ("malloc(): smallbin double linked list corrupted");
          set_inuse_bit_at_offset (victim, nb);
          bin->bk = bck;
          bck->fd = bin;
          if (av != &main_arena)
            set_non_main_arena (victim);
          check_malloced_chunk (av, victim, nb);
#if USE_TCACHE
          /* While we're here, if we see other chunks of the same size,
             stash them in the tcache.  */
          size_t tc_idx = csize2tidx (nb);
          if (tcache && tc_idx < mp_.tcache_bins)
            {
              mchunkptr tc_victim;
              /* While bin not empty and tcache not full, copy chunks over.  */
              while (tcache->counts[tc_idx] < mp_.tcache_count
                     && (tc_victim = last (bin)) != bin)
                {
                  if (tc_victim != 0)
                    {
                      bck = tc_victim->bk;
                      set_inuse_bit_at_offset (tc_victim, nb);
                      if (av != &main_arena)
                        set_non_main_arena (tc_victim);
                      bin->bk = bck;
                      bck->fd = bin;
                      tcache_put (tc_victim, tc_idx);
                    }
                }
            }
#endif
          void *p = chunk2mem (victim);
          alloc_perturb (p, bytes);
          return p;
        }
    }

 

smallbinsのインデックスを取得するのは以下のマクロ

#define smallbin_index(sz) \
  ((SMALLBIN_WIDTH == 16 ? (((unsigned) (sz)) >> 4) : (((unsigned) (sz)) >> 3))\
   + SMALLBIN_CORRECTION)

16==0x10byte単位でbinが作られている場合には

nbを4bitシフトしてidxを得ている

しかしこれだとfastbinsに相当する分のサイズ、つまりsmallbinsでは使われないサイズのインデックスができてしまうのではと思った。。。

 

まあ先に進もう

続いてのbin_atマクロは以下のように展開される

#define bin_at(m, i) \
  (mbinptr) (((char *) &((m)->bins[((i) - 1) * 2]))                              \
             - offsetof (struct malloc_chunk, fd))
//glibc/intl/bindtextdom.c
#ifndef offsetof
# define offsetof(type,ident) ((size_t)&(((type*)0)->ident))
#endif

例えばnb==0xN0の場合にはbin_at()ではbins[N-1]のアドレスが返されるようである

これならbins[0]が存在しないというコメントにも納得がいく

とすると一つのサイズのbinあたり配列2つ分割り当てられてることになるが、それぞれどう使われてるんだ?

 

先へ進みbinのリストにchunkが繋がっていれば一番最後のものをvictimにする

ここでチェック機構

victimの1個前のchunkのfdがvictim自身でなければ

"malloc(): smallbin double linked list corrupted"

というエラーを吐く

 

 

その後set_inuse_bit_at_offset macroによってsize情報から次のchunkのPREV_INUSEフラグを立てる

そしてvictimを取り出した分リストをつなぎ替える

(あれ、binsってFIFOだったよな。そしてら"最後"じゃなくて"最初"のchunkから取ってくるんじゃないのかな。。。)

 

次のcheck_malloced_chunk macroはテストマクロで実体なし

その後以降の処理はfastbinsのときと全く同じで

同じサイズのtcacheに空きがあれば移し替えて

獲得したvictimからユーザランドのアドレスを取得し返す

 

 

以上でfastbinsの処理が終わりになる





5: largebins処理の前の統合処理

largebinsの処理を行う前に以下の統合処理が行われる

  else
    {
      idx = largebin_index (nb);
      if (atomic_load_relaxed (&av->have_fastchunks))
        malloc_consolidate (av);
    }

ここでmalloc_consolidate()が呼ばれているが

これはこれでまたやることが多そうなので

本エントリはここまでにする






続く・・・