ptmalloc2의 구현 목표
1. 메모리 낭지 방지
- 메모리 할당 요청이 발생하면, 먼저 해제된 메모리 공간 중에서 재사용할 수 있는 공간이 있는지 탐색한다.
- 해제된 메모리 공간들 중 동일한 사이즈의 메모리가 요청되면 재사용하며, 작은 크기의 할당이 요청되면 해제된 메모리 공간을 나누어 주기도 한다.
2. 빠른 메모리 재사용
- 특 정 메모리 공간을 해제한 이후에 이를 빠르게 재사용하려면 해제된 메모리 공간의 주소를 기억하고 있어야 한다.
이를 위해 ptmalloc은 메모리 공간 해제 시, tcache 또는 bin이라는 연결 리스트에 해제된 공간의 정보를 저장한다.
3. 메모리 단편화 방지
- 내부/외부 단편화를 줄이기 위해 정렬, 병합, 분할을 사용한다.
- ptmalloc은 64bit 환경 기준, 메모리 공간을 16바이트 단위로 할당해주어 내부 단편화가 생길 지 언정, 외부 단편화를 줄이는 방향으로 할당한다.
ptmalloc2의 객체
1. 청크
2. bin
3. tcahe
4. arena
1. 청크
청크는 헤더와 데이터로 구성되며, 헤더(prev_size,size,A,M,P...)에는 청크 관리에 필요한 정보를, 데이터에는 사용자가 입력한 데이터가 저장된다.
동적으로 할당된 힙 메모리는 하나의 청크라고 불리며, 청크가 사용하는 malloc_chunk 구조체는 다음과 같다.
struct malloc_chunk {
INTERNAL_SIZE_T prev_size; /* Size of previous chunk (if free). */
INTERNAL_SIZE_T 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;
};
- prev_size (8바이트) : 이전의 힙 청크가 해제되었을 때, 해제된 힙 청크의 크기를 나타낸다. 만약 아무 청크가 해제되기 전이라면, 데이터 영역으로 사용
- size (8바이트) : 현재 할당된 힙 청크의 크기 + 3개의 bit flag(하위 3 bit)가 존재한다.
allocated arena / a : 현재 청크가 main_arena에서 관리하지 않을 경우에 설정
prev-in-use / p : 직전 청크가 사용 중인 지를 나타내며, 이전 힙 청크가 해제된 경우에 1로 설정된다.
mmap'd / m : 현재 청크가 mmmap 시스템 콜을 사용하여 할당된 경우 설정된다.
- fd (forward pointer) : 해제 시, bin 연결리스트에서 다음 청크를 가리킨다.
- bk (backward pointer) : 이전 청크를 가리킨다.
- fd_nextsize : large bin에서 사용하는 포인터로, 현재 힙 청크 크기보다 작은 힙 청크의 주소를 가리킨다.
- bk_nextsize : 현재 힙 청크 크기보다 큰 힙 청크의 주소를 가리킨다.
청크의 종류
Allocate Chunk
- malloc, calloc함수 등의 동적 메모리 할당 함수를 통해 할당된 청크를 의미한다.
Free Chunk
- free 함수 등의 동적 메모리 해제 함수를 통해 해제된 청크를 의미한다.
Top Chunk
- 힙 메모리의 마지막에 위치해있는 청크를 의미한다. 만약 메모리 할당 요청 시에 적절한 Free chunk가 없으면 Top chunk를 쪼갈내서 사용한다.
Last Remainder Chunk
- Free chunk가 쪼개지고 남은 청크를 말한다.
2. bin
bin은 사용이 끝난 청크들이 저장되는 객체이다. 해제된 힙 청크는 bin이라는 freelist 구조체를 통해 관리된다.
freelist는 동적으로 메모리를 할당 및 해제 시에 메모리 관리 효율을 높이기 위해 해제된 영역들을 관리하는 연결리스트로
해제하려는 영역을 freelist에 추가하고, 할당 요청 시 freelist에서 추가된 영역을 제거하고 사용한다.
ptmalloc2에서 사용하는 bin들은 다음과 같다.
fastbin
- 32~128 바이트
- 7개의 bin
다른 bin과는 달리 단일 연결 리스트를 사용하며, 메모리 검증 루틴이 적기에 이름 그대로 속도가 빠르다.
LIFO 방식으로 청크를 처리하며, 다른 두개의 청크가 인접해 있어도 하나의 청크로 병합되지 않는다.(consolidation x)
free 시에 해당 128바이트 이하의 크기를 가지면, fastbin 리스트를 가져와 이전 청크의 주소를 현재 청크의 FD에 저장하여 단일 리스트에 추가한다.
malloc 시에 요청된 크기와 부합하는 fastbin의 인덱스를 찾고,
현 FD가 가리키는 이전 청크의 FD를 fastbin의 첫 번째 리스트로 업데이트하여 LIFO구조를 유조한다.
unsortedbin
- small/large bin 크기의 청크가 해제되면 재할당을 위해 사용하는 bin
1개만 존재, 크기의 제한이 없고 분류되지 않은 상태로 다양하게 저장될 수 있다. 이중연결 리스트를 사용하며, FIFO 방식으로 운영한다.
smallbin 크기에 해당하는 청크를 할당 요청하면, ptmalloc은 fastbin 또는 smallbin을 탐색한 뒤 unsortedbin을 탐색한다. largebin의 크기에 해당하는 청크는 unsortedbin을 먼저 탐색한다. unsortedbin에서 적절한 청크가 발견되면 해당 청크를 꺼내어 사용합니다. 이 과정에서, 탐색된 청크들은 크기에 따라 적절한 bin으로 분류된다.
이를 통해 불필요한 연산을 줄이고, 성능을 최적화한다.
(할당 과정)
unsortedbin의 size와 요청이 들어온 nb를 비교 시,
- unsortedbin1 : 동일한 경우
/* Take now instead of binning if exact fit */
INTERNAL_SIZE_T nb; /* normalized request size */
checked_request2size (bytes, nb);
size = chunksize (victim);
if (size == nb)
{
set_inuse_bit_at_offset (victim, size);
if (av != &main_arena)
victim->size |= NON_MAIN_ARENA;
check_malloced_chunk (av, victim, nb);
void *p = chunk2mem (victim);
alloc_perturb (p, bytes);
return p;
}
기존의 unsorted bin에 들어간 영역을 재사용
- unsortedbin2 :
smallbin에 속하며(32~1024) unsorted bin에 저장된 청크 크기보다 작으며,
unsorted bin에 존재하는 청크가 분할된 last_remainder 청크인 경우
if (in_smallbin_range (nb) &&
bck == unsorted_chunks (av) &&
victim == av->last_remainder &&
(unsigned long) (size) > (unsigned long) (nb + MINSIZE))
{
/* split and reattach remainder */
remainder_size = size - nb;
remainder = chunk_at_offset (victim, nb);
unsorted_chunks (av)->bk = unsorted_chunks (av)->fd = remainder;
av->last_remainder = remainder;
remainder->bk = remainder->fd = unsorted_chunks (av);
if (!in_smallbin_range (remainder_size))
{
remainder->fd_nextsize = NULL;
remainder->bk_nextsize = NULL;
}
set_head (victim, nb | PREV_INUSE | (av != &main_arena ? NON_MAIN_ARENA : 0));
set_head (remainder, remainder_size | PREV_INUSE);
set_foot (remainder, remainder_size);
check_malloced_chunk (av, victim, nb);
void *p = chunk2mem (victim);
alloc_perturb (p, bytes);
return p;
}분할하여 남은 청크를 unsorted bin과 last_remainder에 저장
- unsortedbin3 : 다음 할당요청까지 small bin의 크기가 unsorted bin에 남아있다면
if (in_smallbin_range (size))
{
victim_index = smallbin_index (size);
bck = bin_at (av, victim_index);
fwd = bck->fd;
}
victim->bk = bck;
victim->fd = fwd;
fwd->bk = victim;
bck->fd = victim;해당 청크는 smallbin으로 옮겨지고 small bin에서 크기에 적합한 배열을 찾아 존재하는 청크와 FD,BK를 연결
- unsortedbin4 : 다음 할당요청까지 largebin의 크기가 unsortedbin에 남아있다면
else
{
victim_index = largebin_index (size);
bck = bin_at (av, victim_index);
fwd = bck->fd;
if (fwd != bck)
{
/* Or with inuse bit to speed comparisons */
size |= PREV_INUSE;
/* if smaller than smallest, bypass loop below */
assert ((bck->bk->size & NON_MAIN_ARENA) == 0);
if ((unsigned long) (size) < (unsigned long) (bck->bk->size))
{
fwd = bck;
bck = bck->bk;
victim->fd_nextsize = fwd->fd;
victim->bk_nextsize = fwd->fd->bk_nextsize;
fwd->fd->bk_nextsize = victim->bk_nextsize->fd_nextsize = victim;
}
else
{
assert ((fwd->size & NON_MAIN_ARENA) == 0);
while ((unsigned long) size < fwd->size)
{
fwd = fwd->fd_nextsize;
assert ((fwd->size & NON_MAIN_ARENA) == 0);
}
if ((unsigned long) size == (unsigned long) fwd->size)
/* Always insert in the second position. */
fwd = fwd->fd;
else
{
victim->fd_nextsize = fwd;
victim->bk_nextsize = fwd->bk_nextsize;
fwd->bk_nextsize = victim;
victim->bk_nextsize->fd_nextsize = victim;
}
bck = fwd->bk;
}
}
else
victim->fd_nextsize = victim->bk_nextsize = victim;
}
victim->bk = bck;
victim->fd = fwd;
fwd->bk = victim;
bck->fd = victim;해당 청크는 largebin 중 적합한 배열을 찾아 largebin에 존재하는 청크와 fd_nextsize, fbk_nextsize를 연결하고, FD, BK를 연결하여 large bin으로 옮겨진다.
- smallbin / largebin 크기의 청크가 해제되면, unsorted bin에 삽입되는 과정이다.
else
clear_inuse_bit_at_offset(nextchunk, 0);
/*
Place the chunk in unsorted chunk list. Chunks are
not placed into regular bins until after they have
been given one chance to be used in malloc.
*/
bck = unsorted_chunks(av);
fwd = bck->fd;
if (__glibc_unlikely (fwd->bk != bck))
{
errstr = "free(): corrupted unsorted chunks";
goto errout;
}
p->fd = fwd;
p->bk = bck;
if (!in_smallbin_range(size))
{
p->fd_nextsize = NULL;
p->bk_nextsize = NULL;
}
bck->fd = p;
fwd->bk = p;
set_head(p, size | PREV_INUSE);
set_foot(p, size);
check_free_chunk(av, p);clear_inuse_bit_at_offset 매크로를 사용하여 인접한 다음 청크의 prev_inuse 비트를 0으로 만들고,
새롭게 해제된 청크를 이중 연결 리스트에 포함시킨다.
largebin범위의 청크가 해제되면, unsorted bin에서는 사용하지 않는 메타데이터 fd_nextsize, bk_nextsize는 null로 지정한다.
smallbin
- 1024바이트(64bit) / 512바이트(32bit) 미만의 청크
- 이중연결리스트 / FIFO / 62개
청크가 해제되면 unsortedbin에 리스트가 추가된 후, smallbin에 할당된다.
해당 bin에는 두 개의 해제된 청크가 인접해있을 수 있으며, 인접해있는 경우 하나의 청크로 병합된다.
largebin
-1024바이트 이상
- 이중연결리스트 / FIFO / 63개
largebin의 인텍스가 증가하면 해당 bin에 저장하는 청크 사이즈가 로그적으로 증가한다.
범위에 해당하는 모든 청크를 보관하기에, 재할당 요청 시 그 안에서 가장 비슷한 청크를 꺼내 재할당한다.
이를 위해, ptmalloc은 largebin안의 크기를 내림차순하여 정렬하며, 재할당 과정에서 앞 뒤 청크들의 연결리스트를 유지하기 위해 unlink가 동반된다.
또한 연속된 largebin 청크는 병합의 대상이 된다 -> 병합이 되면 내림차순 정렬에 의해 재정렬된다.
4.main_arena
main_arena에는 다음과 같이 힙 청크를 관리하기 위한 배열과 포인터가 존재한다.
struct malloc_state
{
/* Serialize access. */
__libc_lock_define (, mutex);
/* Flags (formerly in max_fast). */
int flags;
/* 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;
};
top chunk의 크기(힙의 마지막에 위치한 청크-> 가장 큰 사이즈의 청크)보다 큰 청크를 할당하면
mmap syscall을 하용하여 새로운 페이지를 할당한다.
이렇게 할당된 힙은 main_arena에서 관리하지 않는다.
16, 32바이트의 힙을 할당하고 해제하는 코드는 다음과 같다.
// gcc -o main_arena main_arena.c
#include <stdio.h>
#include <malloc.h>
int main()
{
char *ptr = malloc(0x10);
free(ptr);
char *ptr2 = malloc(0x20);
free(ptr2);
}
구조체를 출력해보자.
gdb-peda$ p main_arena
$1 = {
mutex = 0x0,
flags = 0x0,
fastbinsY = {0x602000, 0x602020, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0},
top = 0x602050,
...fastbinY에 해제된 두개의 힙 주소가 쓰여진 것을 확인할 수 있다.
fastbinY는 fastbin 크기로 할당되고 해제된 힙을 수용하기 위한 배열이다.
동일한 크기의 할당 요청이 들어오면 fastbinY를 참조하여 할당한다.
#include <stdlib.h>
int main()
{
char *ptr = malloc(32);
char *ptr2 = malloc(32);
char *ptr3 = malloc(32);
free(ptr);
free(ptr2);
free(ptr3);
return 0;
}
gdb-peda$ heapinfo
(0x20) fastbin[0]: 0x0
(0x30) fastbin[1]: 0x602060 --> 0x602030 --> 0x602000 --> 0x0
(0x40) fastbin[2]: 0x0
(0x50) fastbin[3]: 0x0
(0x60) fastbin[4]: 0x0
(0x70) fastbin[5]: 0x0
(0x80) fastbin[6]: 0x0
(0x90) fastbin[7]: 0x0
(0xa0) fastbin[8]: 0x0
(0xb0) fastbin[9]: 0x0
top: 0x602090 (size : 0x20f70)
last_remainder: 0x0 (size : 0x0)
unsortbin: 0x0위에서 32바이트의 메모리를 할당했다가 free하였다.
그렇기에 heapinfo를 통해서 보면 동일한 인덱스의 fastbin에 free된 힙 청크의 주소가 단일 연결리스트로 연결된 것을 확인할 수 있다.
fastbin은 LIFO이기에 이후에 또 다른 32바이트의 메모리 요청이 들어온다면, 0x602060 -> 0x602030 -> 0x60200 순으로 힙 청크가 재할당될 것이다.
[Reference]
https://learn.dreamhack.io/569#4
로그인 | Dreamhack
dreamhack.io
'System Hacking' 카테고리의 다른 글
| write-up (0) | 2024.03.30 |
|---|---|
| _IO_FILE (0) | 2024.03.30 |
| SigReturn-Oriented Programming (0) | 2024.03.30 |
| linux library exploit :: __environ (1) | 2024.03.29 |
| linux library exploit :: _rtld_global (0) | 2024.03.28 |