Malloc(2) - Bin (glibc의 ptmalloc2)

1. Bin

Free chunk는 크기와 히스토리에 따라 다양한 목록에 저장되는데, 이를 "bins"라고 한다.
할당자는 할당 요청을 충족시키기 위해, 적합한 청크를 bins에서 신속하게 찾아 재할당한다.
종류 : Fast bin, Small bin, Large bin, Unsorted bin

2. Fast bin

"fastbin"에 포함되는 chunk크기의 범위는 0 ~ 80*sizeof(size_t)/4까지이다.
- M_MXFAST(1)라는 매개변수를 사용해서 "fastbin"에 포함되는 chunk 범위를 설정한다.
"fastbin"의 기본 범위는 0 ~ 64*sizeof(size_t)/4이다.
- 32bit : 64byte (64 * 4/4)
- 64bit : 128byte (64 * 8/4)
- 해당 크기보다 작은 chunk들이 fastbin에 배치되는 것으로, "value"라는 매개변수를 이용해 크기를 변경할 수 있다.
- 매개변수를 최대로 설정하면, 32bit는 최대 80byte(80*4/4)이고 64bit는 최대 160byte(80*8/4)의 상한을 설정할 수 있다.
fast bin을 비활성화하려면, 크기를 0으로 설정하면 된다.

/* /release/2.25/master/malloc/malloc.c  */

566  Symbol            param #   default    allowed param values
567  M_MXFAST          1         64         0-80  (0 disables fastbins)
568  M_TRIM_THRESHOLD -1         128*1024   any   (-1U disables trimming)
569  M_TOP_PAD        -2         0          any
570  M_MMAP_THRESHOLD -3         128*1024   any   (or 0 if no MMAP support)
571  M_MMAP_MAX       -4         65536      any   (0 disables use of mmap)
*/

/* M_MXFAST is a standard SVID/XPG tuning option, usually listed in malloc.h */
#ifndef M_MXFAST
#define M_MXFAST            1
#endif
 
#ifndef DEFAULT_MXFAST
#define DEFAULT_MXFAST     (64 * SIZE_SZ / 4)
#endif

Fastbin은 LIFO(Last in, first out)으로, 마지막으로 해제된 chunk가 먼저 재할당된다.
최대 10개의 bin을 관리할 수 있으며, fastbin의 상한값보다 크기가 작은 chunk들을 관리한다.
- 64bit경우, chunk크기는 16배수이므로 fastbin에 포함되는 청크의 크기는 32, 48, 64, 80, 96, 112이다.
속도 향상을 위해, single-linked list로 구성되어 있다. (다른 bins들은 이중 연결리스트로 구성되어 있음.)
- 같은 크기의 chunk가 해제되면 마지막으로 해제된 chunk의 fd에 새로 해제된 chunk의 mchunkptr이 저장된다.
- bk는 사용하지 않는다.
fastbin에 포함되는 chunk들은 서로 인접해 있어도 병합하지 않는다.

3. Small bin

해당 bin에 포함되는 chunk는 크기가 MIN_LARGE_SIZE보다 작은 chunk들이다.
- 32bit
  - MALLOC_ALIGNMENT는 8이고, SIZE_SZ는 4이다.
  - MIN_LARGE_SIZE는 512((64-0) *8)이다.
- 64bit
  - MALLOC_ALIGNMENT는 16이고, SIZE_SZ는 8이다.
  - MIN_LARGE_SIZE는 1024((64* 0) *16)이다.
64개의 bin들을 관리하며, doubly-linked list로 구성되어 있다.
Small bin은 FIFO(First In, First Out)으로, 먼저 해제된 청크가 먼저 재할당된다.
Small bin에 해당되는 chunk들은 서로 인접하게 배치될 수 없다.
(해당 chunk가 서로 인접해 있을 경우, 하나의 chunk로 병합된다.)

/* /release/2.25/master/malloc/malloc.c  */

1447	#define NBINS             128
1448	#define NSMALLBINS         64
1449	#define SMALLBIN_WIDTH    MALLOC_ALIGNMENT
1450	#define SMALLBIN_CORRECTION (MALLOC_ALIGNMENT > 2 * SIZE_SZ)
1451	#define MIN_LARGE_SIZE    ((NSMALLBINS - SMALLBIN_CORRECTION) * SMALLBIN_WIDTH)
1452 
1453	#define in_smallbin_range(sz)  \
1454	  ((unsigned long) (sz) < (unsigned long) MIN_LARGE_SIZE)

smallbin_index()함수를 이용하여, bin의 인덱스를 확인할 수 있다.
- 해당 함수는 SMALLBIN_WIDTH를 사용해서, 해당 시스템이 32bit인지 64bit인지 확인한다.
- 64bit : chunk 크기를 16으로 나눈다음, 그 값에 SMALLBIN_CORRECTION을 더하는데, 이 값이 bin인덱스이다.
- 32bit : chunk크기를 8로 나눈다.

/* /release/2.25/master/malloc/malloc.c */

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

4. Large bin

Large bin이 포함하는 chunk의 크기가 MIN_LARGE_SIZE와 같거나 큰 chunk들이다.
- 64bit 아키텍처 경우, free chunk의 크기가 1024와 같거나 크면 해당 chunk는 large bin에 배치된다.
Large bin이 포함하는 chunk들은 서로 인접해 있을 경우, 하나의 chunk로 병합된다.
Large bin은 63개의 bin을 사용하며, doubly-linked list로 구성된다.
- Large bin은 Small bin과 다르게, 하나의 bin에 다양한 크기의 chunk들을 보관한다.
- 해당 bin들은 bin내에서 크기별로 정렬되어, 할당의 효율성을 높인다.

/* /release/2.25/master/malloc/malloc.c */

1417	/*
1418	   Indexing
1419	 
1420	    Bins for sizes < 512 bytes contain chunks of all the same size, spaced
1421	       8 bytes apart. Larger bins are approximately logarithmically spaced:
1422	    
1423	       64 bins of size       8
1424	       32 bins of size      64
1425	       16 bins of size     512
1426	        8 bins of size    4096
1427	        4 bins of size   32768
1428	        2 bins of size  262144
1429	        1 bin  of size what's left
1430	    
1431	       There is actually a little bit of slop in the numbers in bin_index
1432	       for the sake of speed. This makes no difference elsewhere.
1433	    
1434	       The bins top out around 1MB because we expect to service large
1435	       requests via mmap.
1436	    
1437	       Bin 0 does not exist.  Bin 1 is the unordered list; if that would be
1438	       a valid chunk size the small bins are bumped up one.
1439	    */

Large bin에 해당하는 chunk들의 인덱스는 largebin_index_32(), largebin_index_64()함수를 이용하여 확인할 수 있다.

/* /release/2.25/master/malloc/malloc.c */


1454    #define largebin_index_32(sz)                                                \
1455      (((((unsigned long) (sz)) >> 6) <= 38) ?  56 + (((unsigned long) (sz)) >> 6) :\
1456       ((((unsigned long) (sz)) >> 9) <= 20) ?  91 + (((unsigned long) (sz)) >> 9) :\
1457       ((((unsigned long) (sz)) >> 12) <= 10) ? 110 + (((unsigned long) (sz)) >> 12) :\
1458       ((((unsigned long) (sz)) >> 15) <= 4) ? 119 + (((unsigned long) (sz)) >> 15) :\
1459       ((((unsigned long) (sz)) >> 18) <= 2) ? 124 + (((unsigned long) (sz)) >> 18) :\
1460       126)
1461    
1462    #define largebin_index_32_big(sz)                                            \
1463      (((((unsigned long) (sz)) >> 6) <= 45) ?  49 + (((unsigned long) (sz)) >> 6) :\
1464       ((((unsigned long) (sz)) >> 9) <= 20) ?  91 + (((unsigned long) (sz)) >> 9) :\
1465       ((((unsigned long) (sz)) >> 12) <= 10) ? 110 + (((unsigned long) (sz)) >> 12) :\
1466       ((((unsigned long) (sz)) >> 15) <= 4) ? 119 + (((unsigned long) (sz)) >> 15) :\
1467       ((((unsigned long) (sz)) >> 18) <= 2) ? 124 + (((unsigned long) (sz)) >> 18) :\
1468       126)
1469    
1470    // XXX It remains to be seen whether it is good to keep the widths of
1471    // XXX the buckets the same or whether it should be scaled by a factor
1472    // XXX of two as well.
1473    #define largebin_index_64(sz)                                                \
1474      (((((unsigned long) (sz)) >> 6) <= 48) ?  48 + (((unsigned long) (sz)) >> 6) :\
1475       ((((unsigned long) (sz)) >> 9) <= 20) ?  91 + (((unsigned long) (sz)) >> 9) :\
1476       ((((unsigned long) (sz)) >> 12) <= 10) ? 110 + (((unsigned long) (sz)) >> 12) :\
1477       ((((unsigned long) (sz)) >> 15) <= 4) ? 119 + (((unsigned long) (sz)) >> 15) :\
1478       ((((unsigned long) (sz)) >> 18) <= 2) ? 124 + (((unsigned long) (sz)) >> 18) :\
1479       126)
1480    
1481    #define largebin_index(sz) \
1482      (SIZE_SZ == 8 ? largebin_index_64 (sz)                                     \
1483       : MALLOC_ALIGNMENT == 16 ? largebin_index_32_big (sz)                     \
1484       : largebin_index_32 (sz))
1485    
1486    #define bin_index(sz) \
1487      ((in_smallbin_range (sz)) ? smallbin_index (sz) : largebin_index (sz)8)

5. Unsorted bin

1개의 bin이 존재하며, doubley-linked list로 관리되는 bin이다.
크기에 상관없이 청크의 재할당을 위해 사용되는 bin이다.
large bin, small bin에서 재할당받고 다시 free()되었을 때 들어가는 bin이다.
(단, fast bin에 해당하는 chunk는 unsorted bin에 배치되지 않는다.)
fastbin의 크기가 아닌 청크를 처음 해제하면, fd와 bk에 main_arena영역의 주소가 들어간다.
( main_arena는 libc.so.6 라이브러리에 존재하는 구조체이기 때문에, libc_leak이 가능해진다.)
같은 크기로 힙을 할당하면,해당 포인터의 fd를 찾아 해당 주소에 재 할당한다.
malloc 요청이 있을 경우에 fast bin, small bin, large bin에서 알맞는 크기의 free chunk를 찾지 못하면 unsorted bin에서 사용가능한 chunk가 있는지 찾는다.

6. 128KB 이상의 큰 메모리

할당자는 크기가 128KB보다 큰 메모리 할당을 위해, mmap()에 새로운 메모리 매핑을 요청한 후 해당 메모리에서 chunk를 할당한다.
- 해당 chunk들은 bin에 속하지 않으며, IS_MMAPPED 플래그가 설정된다.
- 해당 chunk들은 munmap()을 호출하여, 해제한다.

# 참고주소

'System Hacking' 카테고리의 다른 글

Malloc(3) - Arena (glibc의 ptmalloc2) (0)	2022.09.16
Malloc(1) - chunk (glibc의 ptmalloc2) (0)	2022.09.04
Fake EBP (0)	2022.08.03
RTC (Return To CSU) (0)	2022.07.04
RTL (Return to Library) (0)	2022.06.29

d0bbyG

Malloc(2) - Bin (glibc의 ptmalloc2)

1. Bin

2. Fast bin

3. Small bin

4. Large bin

5. Unsorted bin

6. 128KB 이상의 큰 메모리

'System Hacking' 카테고리의 다른 글

티스토리툴바

Malloc(2) - Bin (glibc의 ptmalloc2)

1. Bin

2. Fast bin

3. Small bin

4. Large bin

5. Unsorted bin

6. 128KB 이상의 큰 메모리

'System Hacking' 카테고리의 다른 글

'System Hacking' Related Articles

티스토리툴바