tcacheをgdbで見てみる

tcacheは、スレッドごとにfreeされたヒープ領域をキャッシュしておく仕組みで、パフォーマンスの著しい向上が期待できる。glibc 2.26より導入された。（こちらのサイト より）

自分の環境はglibc 2.31なので、ここからglibc 2.31のソースコードを入手して見てみる。glibc-2.31/malloc/malloc.cにtcache関連のコードは存在していた。

【tcacheについて】

tcacheはtcache_entryと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;

/* There is one of these for each thread, which contains the
  per-thread cache (hence "tcache_perthread_struct").  Keeping
  overall size low is mildly important.  Note that COUNTS and ENTRIES
  are redundant (we could have just counted the linked list each
  time), this is for performance reasons.  */
typedef struct tcache_perthread_struct
{
 uint16_t counts[TCACHE_MAX_BINS];
 tcache_entry *entries[TCACHE_MAX_BINS];
} tcache_perthread_struct;

tcache_perthread_structのentriesでは、64bit環境ではチャンクサイズによって24 ~ 1032バイトまで、16バイト刻みでチャンクを管理している。そのためentriesは合計で64個のエントリを持つことになり、事実TCACHE_MAX_BINSの値は64として定義されていた。

tcache_entryでは、同じチャンクサイズのfreeされたメモリを指すnextと、二重フリーを防止するためにtcache_perthread_structの先頭を指すkeyを持つ。

【tcache_entryの仕組み】

以下のプログラムを動かして動作を見てみる。

// sample.c #include  <stdlib.h> #include  <stdio.h> #include  <string.h>

int main(){

   char *ptr1;
   char *ptr2;
   char *ptr3;
   char *ptr4;
   char *ptr5;
   char *ptr6;

   ptr1 = malloc(0x10);
   ptr2 = malloc(0x10);
   ptr3 = malloc(0x10);
   ptr4 = malloc(0x10);
   ptr5 = malloc(0x20);
   ptr6 = malloc(0x20);

   printf("ptr1: %p, ptr2: %p, ptr3: %p, ptr4: %p, ptr5: %p, ptr6: %p\n", ptr1, ptr2, ptr3, ptr4, ptr5, ptr6);

   free(ptr4);
   free(ptr3);
   free(ptr2);
   free(ptr1);
   free(ptr5);
   free(ptr6);

   return 0;
}

0x10の大きさの動的メモリを4つ、0x20の動的メモリを2つ確保して全てfreeするだけのプログラムである。これを動作させた後、全てのメモリ領域がmallocによって確保されてfreeによって開放された状態のヒープ領域を見てみる。

mallocを行ってfreeした後のヒープ領域は画像のようになっている。ptr1 ~ ptr4までは領域を色付けしてみた。

これらはいずれもtcache_entry構造体である。tcache_entry構造体が

typedef struct tcache_entry
{
 struct tcache_entry *next;
 struct tcache_perthread_struct *key;
} tcache_entry;

であることを思い出すと理解しやすいのではないかと思う。例えばptr1であれば、

tcache_entry *next = 0x5555555592e0

tcache_perthread_struct *key = 0x555555559010

となっていることがわかる。この時のtcache_perthread_structを図示すると以下のようになる。

tcache_entryはLIFO方式である。ptr4 → ptr3 → ptr2 → ptr1の順番でfreeされたため、ptr1がentries[0]の先頭である。

ちなみにentriesの先頭アドレスを書き換えることができれば、次のmallocで任意のアドレスにメモリをallocateできる。これがtcache poisoning攻撃の原理である。

なおptr1やptr2の領域が重なっていることに気づいた方がいるかもしれない。詳しくは本記事最後の参考サイトを見てほしい。端的に言えばメモリchunkの軽量化のためなのだが、解析する際には分かりづらい事この上ない。

【tcache_perthread_structをgdbで見てみる】

ではtcache_perthread_struct構造体はどこに保存されているのであろうか。先程みた通り、*keyはtcache_perthread_structを指している。gdbでこのtcache_perthread_structを見てみる。

*keyが指していたアドレスは0x555555559010だが、例によってchunkのアレによって0x555555559000から領域は始まっている。サイズは先頭から見て0x291だが、tcache_perthread_struct自体の大きさは16バイト引いた0x280（640バイト）である。なお0x555555559000はヒープ領域の先頭でもある。

まずcounts[TCACHE_MAX_BINS]の領域に0x00020004が格納されている。ここでcountsはuint16_tなので一つの領域は2バイトである。リトルエンディアンなのがややこしい点だが、0x00020004はentries[0]のカウントが4, entries[1]が2を表している。

 さらに*entriesの領域を見ていくと、先頭にアドレスが2つ格納されている。これは先程見たptr1, ptr6のアドレスであり、それぞれentries[0], entries[1]を指している。

これによって、tcache_perthread_structの構造体をgdbで見ることができた。

ところでtcache_perthread_struct構造体では、24 ~ 1032バイトのチャンクサイズについて16バイト毎にチャンクを管理している。以下のプログラムのように, entries配列を全て埋め尽くすとどうなるのであろうか。

 #include  <stdio.h> #include  <stdlib.h>

int main(void) {
   char *str[64];

   // 24 bytes
   int size = 24;

   // 16バイト加算しながらmalloc
   for(int i=0; i < 64; i++) {
       str[i] = (char *)malloc(size);
       printf("size %d bytes: %p\n", size, str[i]);
       size += 16;
   }

   printf("max size: %d\n", size - 16);


   // 全てfree
   for(int i=0; i< 64; i++) {
       free(str[i]);
   }

   return 0;
}

entriesの各エントリを埋め尽くすようにメモリを確保した後、全てfreeしてtcache_perthread_structをgdbで確認してみた。

予想通りcountsとentriesが開放したchunkで埋め尽くされていた。

以上より、1032バイト以下の動的メモリはfreeのあとtcacheで管理されること、tcache_perthread_structはヒープ領域に位置していることがわかった。

【参考サイト】

mallocの動作を追いかける(prev_size編) - Qiita

↑ chunkの構造など、とても参考にしました。

glibcのmallocの仕組みを説明したスライド

↑ ヒープ領域全般において、めっちゃ参考にしました。

thread local caching in glibc malloc · Online tukan sanctuary

↑tcacheについて説明したサイト（英語）。このサイトがなかったら記事書いてないと思います。

t-cache poisoning: FireShell CTF 2019 babyheap - ふるつき

↑ 自分がtcacheと出会うきっかけになったサイト。