newbieからバイナリアンへ

newbieからバイナリアンへ

コンピュータ初心者からバイナリアンを目指す大学生日記

【LCR 1.2】LibcCodeReading: malloc編[3]=malloc_consolidate()

 

0: 参考

code.woboq.org

 

 

 

【追記20190924】tcacche/fastbinsの扱いについて追記

【追記20190924】unlink_chunkのマクロ化について追記

【追記20190924】unlinkの処理について追記

 

 

 

1: イントロ

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

前回はlargebinsの処理に入る前の統合処理において

malloc_consolidate()を呼ぶ直前までを扱った

今回はその続きからである




2: malloc_consolidate

 

maxfb = &fastbin (av, NFASTBINS - 1);
  fb = &fastbin (av, 0);
  do {
    p = atomic_exchange_acq (fb, NULL);
    if (p != 0) {
      do {
        {
          unsigned int idx = fastbin_index (chunksize (p));
          if ((&fastbin (av, idx)) != fb)
            malloc_printerr ("malloc_consolidate(): invalid chunk size");
        }
        check_inuse_chunk(av, p);
        nextp = p->fd;
        /* Slightly streamlined version of consolidation code in free() */
        size = chunksize (p);
        nextchunk = chunk_at_offset(p, size);
        nextsize = chunksize(nextchunk);
        if (!prev_inuse(p)) {
          prevsize = prev_size (p);
          size += prevsize;
          p = chunk_at_offset(p, -((long) prevsize));
          if (__glibc_unlikely (chunksize(p) != prevsize))
            malloc_printerr ("corrupted size vs. prev_size in fastbins");
          unlink_chunk (av, p);
        }
//★1
        if (nextchunk != av->top) {
          nextinuse = inuse_bit_at_offset(nextchunk, nextsize);
          if (!nextinuse) {
            size += nextsize;
            unlink_chunk (av, nextchunk);
          } else
            clear_inuse_bit_at_offset(nextchunk, 0);
          first_unsorted = unsorted_bin->fd;
          unsorted_bin->fd = p;
          first_unsorted->bk = p;
          if (!in_smallbin_range (size)) {
            p->fd_nextsize = NULL;
            p->bk_nextsize = NULL;
          }
          set_head(p, size | PREV_INUSE);
          p->bk = unsorted_bin;
          p->fd = first_unsorted;
          set_foot(p, size);
        }
        else {
          size += nextsize;
          set_head(p, size | PREV_INUSE);
          av->top = p;
        }
      } while ( (p = nextp) != 0);
    }
  } while (fb++ != maxfb);

これがおおよそ処理の全て

 

fastbinsの小さい方から順にbinを調べていってchunkがあれば

そのchunkのsizeがbinのidxに適当に対応しているかをチェック

不正なbinに繋がれていることがわかれば

"malloc_consolidate(): invalid chunk size"

というエラーを吐く

 

 

 

その後★1までは次のchunkの情報や一つ前の情報を参照している

PREV_INUSEが下がっている場合にはprev_sizeをもとにして一つ前のchunkのアドレスを計算するのだが

そのchunkのsizeがprev_sizeと異なる場合には

"corrupted size vs. prev_size in fastbins"

というエラーを吐く

 

 

なおnextpで参照される"次の"chunkというのはfastbinのリストによって繋がれた参照関係の"次"という意味であり

その後のチェック機構でprev_sizeなどを参照している"次の"chunkは、heap上で物理的に隣接しているchunkを表している

 

 

********************************************************************************************

*追記を参照のこと*

unlink_chunk()ではbinからchunkを取り外す処理を行う

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

・対象chunkのsizeと(そのsizeをもとにして計算した)次のchunkのprev_sizeが異なる場合:

  "corrupted size vs. prev_size"

・双方向リストの前後のchunkが自分自身を指していない場合

  "corrupted double-linked list"

 

fastbins/smallbinsの場合にはこれで終わりだが

largebinsの場合にはサイズごとの双方向リストもつくられるため

そのリストにおいて整合性が保たれているかのチェックも行われる

ここでは一旦飛ばすことにする

 ******************************************************************************

 

malloc_consolidate()に戻る

続くのは(物理的に)次のchunkの処理である

次の次のchunkのPREV_INUSEが下がっていれば

次のchunkを先ほどと同様の手順でfastbinからリンクを外す

そうでなければ次のchunkのPREV_INUSEを下ろす

 

というかpはfastbinに繋がれているから当然freeであって次のchunkのPREV_INUSEは降りているものと思っていたのだが

fastbinの場合はfreeされても次のchunkのPREV_INUSEは降りないんだっけ。。。?

ココらへんは後にint_free()を見たときに明らかにする

 

続いてunsortedbinの先頭にpを繋ぐ処理をして

size,prev_size,fd,bkを書き込んだら一つのchunkの処理は終了である

 

以上の処理を全てのfastbinの全てのchunkに対して繰り返す

 

 

 

【追記】tcache/fastbinsの扱いについて

tcache/fastbinsはメモリアロケートの観点からすると依然として割り当てられたままである

(glibc 2.27のコメントより)

他のbinsと違い単方向リストで管理されており根本以外のchunkをつなぎ替えることはできないし

統合処理やbk等の記録もなされていない

総合的な位置づけとしては、本来のint_free()を呼ぶわけには行かないから

freeの特別なバージョンとしてmalloc_consolidate()を呼ぶというスタンスであるようだ

 

 

【追記】free_chunkのマクロ化について

自機環境(Ubuntu 18.04.3 LTS/glibc 2.27)に於いてunlink_chunk()の振る舞いをソースデバッグしようとしたところ

$ nm /usr/lib/debug/lib/x86_64-linux-gnu/libc-2.27.so | grep unlink_chunk

シンボル情報がなかった

malloc_consolidate()のディスアセンブリを見てみても関数内で呼ばれているのはmalloc_printerr()のみであった

 

調べてみるとどうやらunlink_chunkはマクロ化されたようだ

どのバージョンからかはわからないが手元のlibc-2.27では既にマクロ化されておりもとの関数は残されていない

マクロの名前はunlink_chunkではなく、unlinkになっている

	if (!prev_inuse(p)) {
	  prevsize = prev_size (p);
	  size += prevsize;
	  p = chunk_at_offset(p, -((long) prevsize));
	  unlink(av, p, bck, fwd);
	}
#define unlink(AV, P, BK, FD) {                                            \
    if (__builtin_expect (chunksize(P) != prev_size (next_chunk(P)), 0))      \
      malloc_printerr ("corrupted size vs. prev_size");			      \
    FD = P->fd;								      \
    BK = P->bk;								      \
    if (__builtin_expect (FD->bk != P || BK->fd != P, 0))		      \
      malloc_printerr ("corrupted double-linked list");			      \
    else {								      \
        FD->bk = BK;							      \
        BK->fd = FD;							      \
        if (!in_smallbin_range (chunksize_nomask (P))			      \
            && __builtin_expect (P->fd_nextsize != NULL, 0)) {		      \
	    if (__builtin_expect (P->fd_nextsize->bk_nextsize != P, 0)	      \
		|| __builtin_expect (P->bk_nextsize->fd_nextsize != P, 0))    \
	      malloc_printerr ("corrupted double-linked list (not small)");   \
            if (FD->fd_nextsize == NULL) {				      \
                if (P->fd_nextsize == P)				      \
                  FD->fd_nextsize = FD->bk_nextsize = FD;		      \
                else {							      \
                    FD->fd_nextsize = P->fd_nextsize;			      \
                    FD->bk_nextsize = P->bk_nextsize;			      \
                    P->fd_nextsize->bk_nextsize = FD;			      \
                    P->bk_nextsize->fd_nextsize = FD;			      \
                  }							      \
              } else {							      \
                P->fd_nextsize->bk_nextsize = P->bk_nextsize;		      \
                P->bk_nextsize->fd_nextsize = P->fd_nextsize;		      \
              }								      \
          }								      \
      }									      \
}

 

 

【追記】unlinkの処理について

fastbinsからunsortedbinsへの繋ぎ変えの理解がてんでだめだったためおさらいする

以下のテストプログラムを動かした

int main(int argc,char *argv[])
{
  void *p[7];
  void *q[3];
  void *r;

  //consume tcache
  for(int ix=0;ix!=7;++ix){
    p[ix] = malloc(0x30);
  }
  for(int ix=0;ix!=3;++ix){
    q[ix] = malloc(0x30);
  }

  for(int ix=0;ix!=7;++ix){
    free(p[ix]);
  }
  for(int ix=0;ix!=2;++ix){
    free(q[ix]);
  }

  //invoke consolidate_malloc()
  getc(stdin);
  r = malloc(0x120);


  return 0;
}

 

上でmalloc_consolidateが呼ばれたとき

qが保持するchunkは

 

chunk0 in fastbin

chunk1 in fastbin

chunk2 in use

(top chunk)

 

となっている

 

malloc_consolidateの処理に於いてまずfastbinY[4]の先頭にあるchunk1が処理される

 

chunk1のPREV_INUSEは立っている(実際chunk0はfree済みだがfastbinに入っているからPREV_INUSEは変更されていない)ため

前方向との統合処理はこの時点で行われない

続いて次のchunkがinuseかどうかを調べるがchunk2はfreeされていないためこの処理も行われない

最後にnextchunkがtopでないかで分岐するがこれは該当する

これによってchunk1のfdとbk及びunsortedbinの先頭のfdとbkが更新されて

chunk1がunsortedbinにつながることになる

この時点でunlinkは一度も使われていない)

また、chunk1のsizeがtopのsizeと加算されて更新される

そしてtopがchunk1を指すように変更される

 

 

次にchunk0の処理が行われるがここでchunk0のPREV_INUSEは立っているため前方との統合はなし

続くnextchunkがinuseかを調べるところで先程chunk2のPREV_INUSEは下ろされているためここで分岐し、後方(chunk1)との統合処理が行われる

その際にunlinkが呼ばれるのだが

注意すべきはこの際にmacroに渡されるのはchunk0ではなくchunk1のアドレスであるということ

先程の処理でchunk1のfd/bkはしっかり書き込まれているから

あとは素直にunlinkの処理に従うだけだ

 

 

なおchunk1に書き込まれているfd/bk/size等は消されるわけではなく

リストに繋がれるのがchunk1からchunk0(+1)になるだけで

meta情報はchunk1の中に残されていいることに注意

このことって、pwnでなんか使えないかな。。。newbieすぎて知らんけど






 

以上でmalloc_consolidate()は終了になる









次回はint_malloc()内のmalloc_consolidate()の続きから扱う

続く・・・