Bin

tcache

#

在 glibc > 2.26的版本才出現

保存

#

typedef struct tcache_perthread_struct
{
  char counts[TCACHE_MAX_BINS];
  tcache_entry *entries[TCACHE_MAX_BINS];
} tcache_perthread_struct;

# define TCACHE_MAX_BINS                64

static __thread tcache_perthread_struct *tcache = NULL;

每個thread都會有一個tcache_perthread_struct，是維護tcache的管理結構

• 第一次呼叫的時候會malloc一塊記憶體存放tcache_perthread_struct(大小為0x290)
• counts:用來記錄每個鏈上面的chunk數量
• entries:chunk的起始點

運作

#

• tcache都會放入chunk直到被填滿(7塊)，被填滿後會把chunk放到對應大小的bins
• malloc時
  • 如果在tcache範圍內，先從tcache裡面找
  • 如果tcache為空，會從fastbin / smallbin / unsortedbin找size符合的
  • 找到對應size的會先將fastbin / smallbin / unsortedbin放到tcache內部，直到填滿
• free時
  • FILO: 會從鍊頭插入和取出chunk
• 不會進行heap consolidation，所以不unset PREV_INUSE bit

  

fastbin

#

保存

#

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;
};
...
typedef struct malloc_chunk* mchunkptr;

struct malloc_state
{
  ...

  /* Fastbins */
  mfastbinptr fastbinsY[NFASTBINS];

  ...
};

• fastbin各個chunk大小的pointer起始點會在被存在main_arena的fastbinsY陣列(main thread)
• 在64位元的系統中以chunk size以0x10遞增:由0x20到0x80
• 當對應大小的tcache滿出來的時候會被存到fastbin
• 一般情況下不會進行合併，所以不unset PREV_INUSE bit
• free時
  • FILO: 會從鍊頭插入和取出chunk

smallbin

#

用來存放中大小的bin，會由unsortedbin轉移

保存

#

struct malloc_state
{
  ...

  mchunkptr bins[NBINS * 2 - 2];

  ...
};

• bins 陣列負責管理unsortedbin/smallbin/largebin鍊的起始點
• 大小為126 1:unsortedbin 263:smallbin 64126:largebin

運作

#

• 進入方式
  • 由unsortedbin放入
• free時
  • FIFO: 會從鍊頭插入chunk，從鍊尾取出chunk(因為是雙向陣列，可以透過bk找到鍊尾)
  • 會進行合併: 若前方或後方的chunk為freed chunk，而合併後的chunk會被插入到unsortedbin

largebin

#

保存

#

smallbin那邊有講，不過size不像是fastbin、smallbin是以0x10遞增的
63條bin鍊總共分為六組，每組有相同的遞增值
ex: 第一組由0x40做遞增，第1條bin鍊:0x4000x430, 第2條bin鍊:0x4400x470

運作

#

• fd_nextsize & bk_nextsize
  • 在同個bin鍊會出現不同的大小，彼此用fd_nextsize/bk_nextsize連接(size會依大小降序排列)
• 進入方式
  • 由unsortedbin放入
• free時
  • FIFO: 會從鍊頭插入chunk中的對應size，從鍊尾取出chunk
  • 會進行合併

unsortedbin

#

如其名，unsortedbin會串聯一堆大小不同的chunk

保存

#

smallbin那邊有講

運作

#

• 以下情況會進入unsortedbin
  • fastbin size < chunk size <= tcache size, tcache該size已滿
  • 要被合併/分割過後的chunk
• free時
  • FIFO: 會從鍊頭插入chunk，從鍊尾取出chunk
• malloc時
  • 在查過 tcache, smallbin之後會去查unsortedbin是否有fit size的chunk
    • 若有則會把該chunk取出
    • 若無
      • 會把分割一塊>該chunk size的chunk(如果有)
      • 並把對應大小的chunk送到smallbin/largebin

References

#

• source code
• 南瓜的簡報
• https://saku376.github.io/2021/06/16/堆溢出利用之fastbin/
• https://www.eet-china.com/mp/a254008.html
• https://ctf-wiki.org/pwn/linux/user-mode/heap/ptmalloc2/implementation/tcache/
• https://blog.csdn.net/qq_41453285/article/details/96865321
• https://medium.com/@soh0ro0t/diving-deep-into-heap-glibc-fastbin-consolidation-4c1f38a70917
• https://tyeyeah.github.io/2021/05/12/2021-05-12-Heap-Exploit-Intro/