2023년 8월 시점에 glibc 2.23에 대해 글을 쓰는 이유
glibc는 버전이 업데이트 될 때마다 새로운 기능을 추가하거나 취약점들을 보완하며, 현재 release된 최신 glibc 버전은 glibc 2.38이다. 그럼
'왜 이런 구닥다리 버전의 glibc를 분석하는 글을 기재하냐?'
라고 물을 수 있는데,
이는 glibc가 업데이트 될 때마다 취약점들을 업데이트하고 새로운 기능들을 추가하긴 하지만, 대부분은 원래 있던 버전의 소스코드에 코드를 "추가" 하는 것이지, 원래 있던 코드를 삭제하고 그것을 "새로 쓰는 것"은 아니기 때문이다.
따라서 한 버전의 glibc를 통해 heap의 동작을 이해한다면, 이후에 나오는 glibc 버전에서는 어떤 요소가 새로 추가되었는지, 또는 변경되었는지만 확인하면 되기 때문에 분석하기가 훨씬 편해진다.
따라서 이후 나올 glibc의 패치 내용을 잘 분석하기 위해, 나는 heap 동작의 기본적인 틀을 이해하고자 glibc 2.23에 대한 분석글을 남겨놓는 것이다.
해당 글은 glibc 2.23을 기준으로 작성됐다.
glibc 코드 출처
https://elixir.bootlin.com/glibc/glibc-2.23/source/malloc/malloc.c
malloc.c - malloc/malloc.c - Glibc source code (glibc-2.23) - Bootlin
/* Malloc implementation for multiple threads without lock contention. Copyright (C) 1996-2016 Free Software Foundation, Inc. This file is part of the GNU C Library. Contributed by Wolfram Gloger and Doug Lea , 2001. The GNU C Library is free software; you
elixir.bootlin.com
main_arena
-힙을 효율적으로 관리하기 위해 존재하는 malloc_state 구조체
-top chunk의 크기보다 큰 사이즈의 할당 요청이 들어오면 mmap 시스템 콜을 사용해 새로운 페이지를 할당한다. 이렇게 할당된 힙은 main_arena에서 관리하지 않는다.
static struct malloc_state main_arena =
{
.mutex = _LIBC_LOCK_INITIALIZER,
.next = &main_arena,
.attached_threads = 1
};struct malloc_state
{
/* Serialize access. */
mutex_t 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;
};malloc_state 구조체의 모습
각 bin에 해당되는 크기
Fastbin
16 ~ 64 바이트 ( 32 bit )
32 ~ 128 바이트 ( 64 bit )
Unsorted bin
Small bin
크기 < 512 바이트 (32 bit)
크기 < 1024 바이트 (64 bit)
Large bin
크기 >= 512 바이트 (32 bit)
크기 >= 1024 바이트 (64 bit)
0-1. 청크 할당 시 쓰이는 _int_malloc()의 지역 변수
static void *
_int_malloc (mstate av, size_t bytes)
{
INTERNAL_SIZE_T nb; /* normalized request size */
unsigned int idx; /* associated bin index */
mbinptr bin; /* associated bin */
mchunkptr victim; /* inspected/selected chunk */
INTERNAL_SIZE_T size; /* its size */
int victim_index; /* its bin index */
mchunkptr remainder; /* remainder from a split */
unsigned long remainder_size; /* its size */
unsigned int block; /* bit map traverser */
unsigned int bit; /* bit map traverser */
unsigned int map; /* current word of binmap */
mchunkptr fwd; /* misc temp for linking */
mchunkptr bck; /* misc temp for linking */
const char *errstr = NULL;0-2. 청크 해제 시 쓰이는 _int_free()의 지역 변수
static void
_int_free (mstate av, mchunkptr p, int have_lock)
{
INTERNAL_SIZE_T size; /* its size */
mfastbinptr *fb; /* associated fastbin */
mchunkptr nextchunk; /* next contiguous chunk */
INTERNAL_SIZE_T nextsize; /* its size */
int nextinuse; /* true if nextchunk is used */
INTERNAL_SIZE_T prevsize; /* size of previous contiguous chunk */
mchunkptr bck; /* misc temp for linking */
mchunkptr fwd; /* misc temp for linking */
const char *errstr = NULL;
int locked = 0;
size = chunksize (p);
0-3. mchunkptr(malloc_chunk 구조체를 가리키는 포인터)에서, 구조체 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;
};
0-4. 구조체 malloc_state의 구조(mstate == 구조체 malloc_state를 가리키는 포인터)
struct malloc_state
{
/* Serialize access. */
mutex_t 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;
};struct malloc_state;
typedef struct malloc_state *mstate;
fastbin
-16 ~ 64 바이트 (32 bit)
32 ~ 128 바이트 (64 bit)
-총 64bit 기준 32byte부터 +16byte 등차로 7개의 리스트가 있으며,
각 리스트에는 최대 9개의 청크가 들어갈 수 있음
-단일 연결 리스트 구조
-LIFO 방식으로 동작
-청크들 병합(X)
fastbin 크기의 청크 해제(free)
if ((unsigned long)(size) <= (unsigned long)(get_max_fast ())
#if TRIM_FASTBINS
/*
If TRIM_FASTBINS set, don't place chunks
bordering top into fastbins
*/
&& (chunk_at_offset(p, size) != av->top)
#endif
) {
if (__builtin_expect (chunk_at_offset (p, size)->size <= 2 * SIZE_SZ, 0)
|| __builtin_expect (chunksize (chunk_at_offset (p, size))
>= av->system_mem, 0))
{
/* We might not have a lock at this point and concurrent modifications
of system_mem might have let to a false positive. Redo the test
after getting the lock. */
if (have_lock
|| ({ assert (locked == 0);
mutex_lock(&av->mutex);
locked = 1;
chunk_at_offset (p, size)->size <= 2 * SIZE_SZ
|| chunksize (chunk_at_offset (p, size)) >= av->system_mem;
}))
{
errstr = "free(): invalid next size (fast)";
goto errout;
}
if (! have_lock)
{
(void)mutex_unlock(&av->mutex);
locked = 0;
}
}
free_perturb (chunk2mem(p), size - 2 * SIZE_SZ);
set_fastchunks(av);
unsigned int idx = fastbin_index(size);
fb = &fastbin (av, idx);
/* Atomically link P to its fastbin: P->FD = *FB; *FB = P; */
mchunkptr old = *fb, old2;
unsigned int old_idx = ~0u;
do
{
/* Check that the top of the bin is not the record we are going to add
(i.e., double free). */
if (__builtin_expect (old == p, 0))
{
errstr = "double free or corruption (fasttop)";
goto errout;
}
/* Check that size of fastbin chunk at the top is the same as
size of the chunk that we are adding. We can dereference OLD
only if we have the lock, otherwise it might have already been
deallocated. See use of OLD_IDX below for the actual check. */
if (have_lock && old != NULL)
old_idx = fastbin_index(chunksize(old));
p->fd = old2 = old;
}
while ((old = catomic_compare_and_exchange_val_rel (fb, p, old2)) != old2);
if (have_lock && old != NULL && __builtin_expect (old_idx != idx, 0))
{
errstr = "invalid fastbin entry (free)";
goto errout;
}
}-Tcache와 상당히 유사하게 작동한다.
[1] Line 1: 현재 해제하려는 청크의 크기가 fastbin에 들어갈 수 있는 최대 크기보다 작은지 검사한다. 조건문을 통과했다면 다음으로 넘어간다.
[2] Line 41: 현재 해제하려는 청크의 크기에 해당하는 fastbin의 리스트를 가져온다.
[3] Line 61: fastbin free-list에 저장돼있던 기존 청크가 존재한다면, 기존 청크의 주소를 지금 해제하려는 청크의 fd에 저장한다.
fastbin에 들어있는 청크 할당
if ((unsigned long) (nb) <= (unsigned long) (get_max_fast ()))
{
idx = fastbin_index (nb);
mfastbinptr *fb = &fastbin (av, idx);
mchunkptr pp = *fb;
do
{
victim = pp;
if (victim == NULL)
break;
}
while ((pp = catomic_compare_and_exchange_val_acq (fb, victim->fd, victim))
!= victim);
if (victim != 0)
{
if (__builtin_expect (fastbin_index (chunksize (victim)) != idx, 0))
{
errstr = "malloc(): memory corruption (fast)";
errout:
malloc_printerr (check_action, errstr, chunk2mem (victim), av);
return NULL;
}
check_remalloced_chunk (av, victim, nb);
void *p = chunk2mem (victim);
alloc_perturb (p, bytes);
return p;
}
}[1] Line 4: 현재 할당 요청된 청크의 크기에 부합하는 fastbin의 인덱스를 찾는다
[2] Line 12: 선택된 청크의 fd를 참조하여 대상 청크의 fd가 가리키는 청크를 fastbin의 첫 번째가 되도록 그리고 이후의 청크들도, 반복문을 통해 리스트를 업데이트 한다.
[3] Line 26: 선택된 청크를 반환해주며, 할당 과정을 종료한다.
unsorted bin
-Fastbin, tcache에 들어가지 않는 Small bin or Large bin 크기 청크가 해제됐을 때 사용되는 bin
-크기 제한(X)
-원형 이중 연결 리스트 구조
-FIFO 방식으로 동작
unsorted bin에 있던 청크의 할당(1, 2) 및 분류(3, 4) 과정
1. unsorted bin에 있는 chunk와 할당 요청을 받은 크기가 일치하는 경우
INTERNAL_SIZE_T nb; /* normalized request size */
checked_request2size (bytes, nb);
size = chunksize (victim);
/* Take now instead of binning if exact fit */
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;
}[0] unsorted bin에 있는 청크의 size와 할당 요청이 들어온 크기인 nb를 비교하여, 둘이 정확히 같은 크기라면 if문이 충족된다( if (size == nb) )
[1] 이후 set_in_use_bit_at_offset()을 통해 할당해줄 청크와 인접한 다음 청크의 PREV_INUSE 플래그를 설정하고
[2] if문을 통해 할당해 청크가 main_arena가 관리하는 청크가 아니라면 NON_MAIN_ARENA 비트를 설정한 후
[3] unsorted bin에 있는 해당 크기(nb)의 청크를 "freed -> malloced"로 정리한 후 return 해준다.
2. [1] 할당 요청이 들어온 크기가 small bin에 속함 && [2] unsorted bin에 청크가 하나만 있음 && [3] unsorted bin에 있는 청크가 last_remainder 청크임 && [4] "할당 요청된 크기 + MINSIZE < 현재 unsorted bin에 들어있는 청크의 크기" 일 경우
/*
If a small request, try to use last remainder if it is the
only chunk in unsorted bin. This helps promote locality for
runs of consecutive small requests. This is the only
exception to best-fit, and applies only when there is
no exact fit for a small chunk.
*/
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;
}Line1의 /* 주석 */ 을 살펴보면: 작은 크기의 요청일 때, unsorted bin에 있는 유일한 청크가 last_remainder 청크라면 이를 사용한다. 이는 작은 크기의 요청에 대한 exact fit이 존재하지 않을 경우에 적용된다고 적혀있다.
이 경우, unsorted bin의 청크가 어떤 동작을 통해 할당되는지 살펴보자.
/* 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);[1] remainder_size를 "현재 size - 요청받은 size"로 갱신해준다.
[2] remainder 포인터를 갱신한다.
[3] unsorted bin의 fd와 bk를 remainder에 맞게 갱신한다
[4] malloc_state의 last_remainder를 갱신한다
[5] remainder의 bk와 fd를 unsorted bin을 가리키게 갱신한다. (unsorted bin은 이중 연결 리스트(double-linked-list)이기 때문)
if (!in_smallbin_range (remainder_size))
{
remainder->fd_nextsize = NULL;
remainder->bk_nextsize = NULL;
}[1] 위에서 갱신한 remainder_size가 large bin에 해당하는 크기일 경우(== small bin에 해당하는 크기가 아닐 경우), large bin에만 쓰이는 요소인 fd_nextsize와 bk_nextsize를 NULL로 세팅해준다. (large bin은 일정 범위의 크기를 갖는 청크들을 하나의 리스트에 담아놓기 때문에, fd_nextsize와 bk_nextsize는 인접한 사이즈를 가진 청크를 가리키는 데 사용된다.)
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);
/* Line 8 ~ Line 15: set_head_size, set_head, set_foot 함수에 관한 정보
/* Set size at head, without disturbing its use bit */
#define set_head_size(p, s) ((p)->size = (((p)->size & SIZE_BITS) | (s)))
/* Set size/use field */
#define set_head(p, s) ((p)->size = (s))
/* Set size at footer (only when chunk is not in use) */
#define set_foot(p, s) (((mchunkptr) ((char *) (p) + (s)))->prev_size = (s))
*/[1] set_head 함수를 통해 "할당될 청크의 size, 플래그"를 설정해준다
[2] set_head 함수를 통해 remainder 청크의 size와 플래그를 갱신해준다
[3] set_foot 함수를 통해 remainder 이후 청크의 prev_size를 remainder 청크의 크기로 갱신해준다.
check_malloced_chunk (av, victim, nb);
void *p = chunk2mem (victim);
alloc_perturb (p, bytes);
return p;그리고 할당해주려던 청크를 "freed chunk -> malloced chunk"로 변환한 뒤 반환해준다.
3. 다음 할당 요청까지 small bin 크기의 청크가 unsorted bin에 있을 경우 -> small bin으로 청크 이동시킴
if (in_smallbin_range (size))
{
victim_index = smallbin_index (size);
bck = bin_at (av, victim_index);
fwd = bck->fd;
}
mark_bin (av, victim_index);
victim->bk = bck;
victim->fd = fwd;
fwd->bk = victim;
bck->fd = victim;[1] if문을 통해 청크의 size가 small bin에 들어갈 크기인지 검사한다
[2] if문을 통과했다면, 이 청크의 사이즈에 맞는 small bin의 index를 찾은 뒤 victim_index에 저장하고,
[3] 내 이전에 있는 청크(bck)는 small bin 주소로, 내 앞에 있던 청크(fwd)는 bck->fd(small bin의 해당 index bin에 가장 앞에 있던 청크)로 설정해준다.
[4] 그 후 if문을 빠져나와 mark_bin을 통해 binmap을 업데이트 시켜준다.(mark_bin은 binmap을 세팅해줄 때 쓰이는 함수로, binmap은 해당 bin에 청크가 있는지 유무를 알려주는 함수이다.)
[5] 그리고 현재 small bin으로 이동된 청크의 bk에는 bck(==small bin)의 주소를, fd에는 이후 청크의 주소를 넣어주고
[6] 이후 청크의 bk에는 이동된 청크의 주소, 이전 청크(== bck == small bin)의 fd에도 이동된 청크의 주소를 넣어준다.
4. 다음 할당 요청까지 large bin 크기의 청크가 unsorted bin에 있을 경우 -> large bin으로 청크 이동시킴
else
{
victim_index = largebin_index (size);
bck = bin_at (av, victim_index);
fwd = bck->fd;
/* maintain large bins in sorted order */
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;
}
mark_bin (av, victim_index);
victim->bk = bck;
victim->fd = fwd;
fwd->bk = victim;
bck->fd = victim;[0] else문은 3.번에서의 if문과 이어져 있는 else문이다. else(만약 small bin에 들어갈 크기가 아니라면 == large bin에 해당하는 크기라면)
else
{
victim_index = largebin_index (size);
bck = bin_at (av, victim_index);
fwd = bck->fd;[1] 해당 청크의 size에 맞는 인덱스의 large bin을 찾아 victim_index에 저장한다
[2] bck를 victim_index에 맞는 large bin의 주소로 설정한다
[3] fwd를 bck의 fd 값으로 설정한다
/* maintain large bins in sorted order */
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;
}[0-1] large bin은 하나의 index bin 안에 특정 범위를 갖는 청크들을 모두 보관하여 내림차순으로 정렬하여두므로, large bin의 구조를 유지하기 위해 여러 조건문들이 존재한다. 하나하나 살펴보도록 하자.
[0-2] if문을 통해 이후의 청크(fwd)와 이전의 청크(bck == 지금은 large bin의 주소임)가 같지 않다면.
즉, large bin이 비어있는 상태가 아니라면(large bin은 이중 연결 리스트이기 때문에 fwd == bck면 large bin이 비어있는 상태라는 뜻임)
if문을 통과하게 된다
[1] size와 PREV_INUSE를 or 해주고(/* 주석 */을 보면 비교를 더 빠르게 하기 위해 이렇게 해준다고 돼있는데, 나도 정확한 원리는 모르겠다), 그리고 assert는 DEBUG 모드에서만 실행되는 함수라고 malloc.c의 Line 280에 정의되어 있다. 따라서 assert()는 아무런 역할도 하지 않는다.
[2] 현재 추가할 청크의 size가 해당 인덱스의 large bin에 존재하는 가장 작은 크기인 chunk의 size보다 작다면 아래의 if문이 실행된다( (a) large bin은 circular doubly linked list이므로 bck->bk는 large bin의 가장 마지막에 위치해있는 청크를 뜻한다.
(b) 이때 large bin은 크기에 따라 내림차순으로 정리되어 있기 때문에, large bin의 마지막에 위치해있는 chunk는 가장 크기가 작은 chunk이다. )
[3] if문이 실행되어
(a) fwd(자신의 이후에 위치하는 청크)를 해당 인덱스 large bin의 주소로 설정하고,
(b) bck(자신의 이전에 위치하는 청크)는 현재 large bin에 존재하는 크기가 가장 작은 청크로 설정해준다
(c) large bin에 추가하려는 청크의 fd_nextsize를 현재 large bin의 첫번째 청크로 설정하고,
(d) 현재 추가하려는 청크의 bk_nextsize를 large bin에 있었던 원래 가장 작은 크기의 청크로 설정해준다.
(e) large bin에 있는 원래 가장 작은 크기였던 청크의 fd_nextsize와 large bin에 존재하는 가장 큰 크기의 chunk의 bk_nextsize를 현재 추가할 청크(원래 large bin에 있던 가장 작은 크기의 청크보다 작은 크기의 청크)로 설정해준다.
[3]의 (a) ~ (e)의 과정은 large bin의 circular doubly linked list 구조를 유지하기 위한 일련의 과정이라고 생각하면 된다.
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;
}
}[0]
if ((unsigned long) (size) < (unsigned long) (bck->bk->size))이 아닌 경우라면. 즉, large bin에 추가할 청크의 size가 현재 large bin에 있는 가장 작은 크기의 청크 size보다 크다면
[1]
while ((unsigned long) size < fwd->size)
{
fwd = fwd->fd_nextsize;
assert ((fwd->size & NON_MAIN_ARENA) == 0);
}(a) while문을 통해 "(현재 추가할 청크의 size) < fwd->size"일 동안
(b) fwd = fwd->fd_nextsize;를 반복한다. 이것의 수행 결과 우리가 넣어줄 청크는 large bin에서 자신의 자리를 찾아 위치하게 된다.
[2] while문 탈출 이후
if ((unsigned long) size == (unsigned long) fwd->size)
/* Always insert in the second position. */
fwd = fwd->fd;를 통해 "추가할 청크의 size == 추가할 청크 이후 청크의 size"라면. 즉, 추가할 청크와 같은 크기의 청크가 있다면
현재 추가할 청크를 원래 위치하던 같은 크기의 청크 뒤에 위치하게 한다.
[3]
else
{
victim->fd_nextsize = fwd;
victim->bk_nextsize = fwd->bk_nextsize;
fwd->bk_nextsize = victim;
victim->bk_nextsize->fd_nextsize = victim;
}
bck = fwd->bk;
}[2]에 해당하는 경우가 없다면, else문 아래가 실행된다. 현재 우리가 추가할 청크는 large bin에서 자신의 위치를 잡은 상태이다.
(a) 추가할 청크의 fd_nextsize와 bk_nextsize, 그리고 이전 청크의 fd_nextsize와, 이후 청크의 bk_nextsize를 세팅해준다.
(b) 그 후 bck = fwd->bk를 통해 현재 추가할 청크를 large bin에 추가할 세팅을 마치고
(c) else문(현재 추가할 청크가 large bin에 있는 가장 작은 사이즈의 크기보다 작은 청크가 아닐 경우)을 빠져나오게 된다.
else
victim->fd_nextsize = victim->bk_nextsize = victim;
}large bin이 비어있었던 경우, if(large bin이 비어있지 않은 경우)-else(large bin이 비어있는 경우)문에서 else문(large bin이 비어있는 경우)가 실행되어,
(a) 현재 추가할 청크의 fd_nextsize와 bk_nextsize를 자기 자신을 가리키게 설정한다.
mark_bin (av, victim_index);
victim->bk = bck;
victim->fd = fwd;
fwd->bk = victim;
bck->fd = victim;small bin 또는 large bin에 unsorted bin에 있던 청크를 넣는 것을 마친 후(3 small bin으로 이동시킴, 4 large bin으로 이동시킴) 위의 코드를 통해
(a) mark_bin을 통해 binmap을 업데이트 시켜준다.(mark_bin은 binmap을 세팅해줄 때 쓰이는 함수로, binmap은 해당 bin에 청크가 있는지 유무를 알려주는 함수이다.)
(b) 현재 추가한 청크의 fd와 bk값, 그리고 fwd의 bk와, bck의 fd 값을 적절히 세팅해줌으로서, unsorted bin에 있던 청크를 small bin 또는 large bin으로 분류하는 과정을 마치게 된다.
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);
}[1] Line 2를 통해 인접한 다음 청크의 PREV_INUSE 비트를 0으로 초기화 해준다.
[2] bck == unsorted bin의 주소, fwd == unsorted bin의 첫 번째 청크로 설정한다
[3] 현재 unsorted bin에 추가할 청크의 fd, bk 값을 초기화 해준다.
[4] 현재 추가할 청크의 크기가 large bin 크기 범위에 속하는 청크라면 large bin에서만 쓰이는 fd_nextsize와 bk_nextsize를 NULL로 세팅해준다
[5] bck->fd와 fwd->bk가 현재 추가할 청크를 가리키게 하고
[6] set_head와 set_foot 함수를 통해 현재 unsorted bin으로 free될 청크의 size와 PREV_INUSE flag를 설정해주고, free될 청크에 인접한 다음 청크의 prev_size를 현재 free될 청크의 size로 세팅해준다.
[7] check_free_chunk를 통해 free가 잘 되었는지 확인한다.
__glibc_unlikely()에 대해서는 이후 글에서 다루도록 하겠다.
small bin
- 청크가 해제 됐을 때 unsorted bin에 추가된 후 저장되는 bin
- 크기 < 512 바이트 (32 bit)
크기 < 1024 바이트 (64 bit)
- bin의 개수 == 62개 (+64비트 기준 0x10byte씩 등차)
- 원형 이중 연결 리스트
- FIFO 구조
- 하나의 bin에 두 개의 해제된 청크가 인접해 있을 수 없음. -> 인접한 경우 하나로 병합(consolidate)됨.
small bin에 있던 청크가 할당(malloc) 되는 과정
/*
If a small request, check regular bin. Since these "smallbins"
hold one size each, no searching within bins is necessary.
(For a large request, we need to wait until unsorted chunks are
processed to find best fit. But for small ones, fits are exact
anyway, so we can check now, which is faster.)
*/
if (in_smallbin_range (nb))
{
idx = smallbin_index (nb);
bin = bin_at (av, idx);
if ((victim = last (bin)) != bin)
{
if (victim == 0) /* initialization check */
malloc_consolidate (av);
else
{
bck = victim->bk;
if (__glibc_unlikely (bck->fd != victim))
{
errstr = "malloc(): smallbin double linked list corrupted";
goto errout;
}
set_inuse_bit_at_offset (victim, nb);
bin->bk = bck;
bck->fd = bin;
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;
}
}
}/* 주석 */: small bin 크기에 해당하는 할당 요청의 경우에는 exact-fit을 할당하면 되기에, best-fit을 탐색해야 하는 large bin 크기에 대한 할당보다 속도가 빠르다는 얘기.
if (in_smallbin_range (nb))
{
idx = smallbin_index (nb);
bin = bin_at (av, idx);[1] if문을 통해 할당 요청이 들어온 크기(==nb)가 small bin에 해당하는 크기인지 확인
[2] idx = 할당 요청이 들어온 크기에 맞는 small bin의 인덱스
bin = bin_at함수를 통해 구한 idx에 해당하는 small bin의 주소
if ((victim = last (bin)) != bin)
{
if (victim == 0) /* initialization check */
malloc_consolidate (av);
/* Reminders about list directionality within bins */
#define first(b) ((b)->fd)
#define last(b) ((b)->bk)[3] if문을 통해 victim = last(bin)을 해주고 small bin이 비어있는 상태가 아니라면 Line 1의 if문이 충족된다.
[4] if ( victim == 0(NULL) )인 경우 malloc()이 처음 호출되어 bin이 초기화 돼있지 않은 상태인 것이다. 따라서 malloc_consolidate()를 호출하여 bin을 초기화 해준다. 이 초기화의 결과로 bin은 자기자신을 가리키게 된다.
else
{
bck = victim->bk;
if (__glibc_unlikely (bck->fd != victim))
{
errstr = "malloc(): smallbin double linked list corrupted";
goto errout;
}
set_inuse_bit_at_offset (victim, nb);
bin->bk = bck;
bck->fd = bin;
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;
}
}
}[5] victim != NULL인 경우엔 small bin에 청크가 존재하고, bin 또한 이미 초기화 되어있는 상태이니, else문이 실행된다.
[6] bck = victim->bk(small bin의 주소)
[7] set_inuse_bit_at_offset (victim, nb)를 통해 victim과 인접한 다음 청크의 PREV_INUSE 비트를 설정해준다.
[8] bin->bk가 현재 인덱스의 small bin을 가리키게 하고, bck->fd가 현재 인덱스의 small bin을 가리키게 한다. (circular doubly linked list 구조를 유지하기 위함)
[9] 현재 할당될 청크가 main_arena의 관리하는 청크가 아닐 경우 해당 청크의 NON_MAIN_ARENA 플래그를 설정하고
[10] Line 32 ~ Line 35의 과정을 통해 malloced 청크로 만들어준 후, 해당 청크를 할당시켜준다.
small bin 크기의 청크가 free 됐을 때의 동작은 unsorted bin에 기재되어 있다.
large bin
- 청크가 해제 됐을 때 unsorted bin에 추가된 후 저장되는 bin
- 크기 >= 512 바이트 (32 bit)
크기 >= 1024 바이트 (64 bit)
- bin의 개수 == 63
- 원형 이중 연결 리스트
- FIFO 구조
- large bin에서만 bk_nextsize와 fd_nextsize가 쓰임
- 다른 bin들과 다르게 하나의 bin에 특정한 크기의 청크들만 들어가는 것이 아니라 <-> 일정 범위 안의 크기를 갖는 청크들이 하나의 bin에 크기 내림차순으로 정리되어 보관됨
- 서로 인접한 청크들은 서로 병합된다.
- best-fit으로 동작하기 때문에 할당 요청을 처리하기 위해 하나의 청크가 쪼개질 수도 있다.
large bin에 있던 청크가 할당(malloc)되는 과정
/*
If a large request, scan through the chunks of current bin in
sorted order to find smallest that fits. Use the skip list for this.
*/
if (!in_smallbin_range (nb))
{
bin = bin_at (av, idx);
/* skip scan if empty or largest chunk is too small */
if ((victim = first (bin)) != bin &&
(unsigned long) (victim->size) >= (unsigned long) (nb))
{
victim = victim->bk_nextsize;
while (((unsigned long) (size = chunksize (victim)) <
(unsigned long) (nb)))
victim = victim->bk_nextsize;
/* Avoid removing the first entry for a size so that the skip
list does not have to be rerouted. */
if (victim != last (bin) && victim->size == victim->fd->size)
victim = victim->fd;
remainder_size = size - nb;
unlink (av, victim, bck, fwd);
/* Exhaust */
if (remainder_size < MINSIZE)
{
set_inuse_bit_at_offset (victim, size);
if (av != &main_arena)
victim->size |= NON_MAIN_ARENA;
}
/* Split */
else
{
remainder = chunk_at_offset (victim, nb);
/* We cannot assume the unsorted list is empty and therefore
have to perform a complete insert here. */
bck = unsorted_chunks (av);
fwd = bck->fd;
if (__glibc_unlikely (fwd->bk != bck))
{
errstr = "malloc(): corrupted unsorted chunks";
goto errout;
}
remainder->bk = bck;
remainder->fd = fwd;
bck->fd = remainder;
fwd->bk = remainder;
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;
}
}
if (!in_smallbin_range (nb))
{
bin = bin_at (av, idx);[1] 할당 요청이 들어온 크기(nb)가 large bin 크기에 속한다면, if문이 충족된다.
bin_at()을 통해 "bin = 할당 요청 크기에 맞는 large bin 인덱스의 주소"
/* skip scan if empty or largest chunk is too small */
if ((victim = first (bin)) != bin &&
(unsigned long) (victim->size) >= (unsigned long) (nb))
{
victim = victim->bk_nextsize;
while (((unsigned long) (size = chunksize (victim)) <
(unsigned long) (nb)))
victim = victim->bk_nextsize;[2] victim = large bin의 첫 번째에 있는 청크(크기가 가장 큰 청크)
[3] if문을 통해 (large bin이 비어있지 않음) && (large bin에서 크기가 가장 큰 청크의 size >= 할당 요청이 들어온 size)
라면 if문을 만족한다.
[4] victim = victim->bk_nextsize 를 통해 "victim = large bin에서 크기가 가장 작은 청크"로 설정해준다. (large bin은 circular doubly linked list임을 유념하자)
[5] 그 후 while문을 통해 "(size = victim의 size) < (할당 요청이 들어온 size)"일 동안
victim = victim -> bk_nextsize를 통해 (a) large bin에서 nb와 size가 가장 근접하지만, (b) nb보다 size가 큰 청크를 탐색하여, (c) 그 청크를 victim으로 설정해준다.
/* Avoid removing the first entry for a size so that the skip
list does not have to be rerouted. */
if (victim != last (bin) && victim->size == victim->fd->size)
victim = victim->fd;
remainder_size = size - nb;
unlink (av, victim, bck, fwd);/* 주석 */ skip list는 메모리 청크의 크기별로 정렬된 연결 리스트를 관리하며, 크기가 같은 청크가 여러 개 있다면, 이들은 동일한 크기 레벨의 skip list 노드에 연결된다. 따라서 skip list를 재정렬하지 않도록,
크기가 같은 청크들이 있다면 첫 번째 청크가 아닌 인접한 청크들 중 이후의 청크를 쓰도록 한다.
[6] ( [5]에서 설정한 victim이 large bin의 마지막 청크가 아닐 경우 ) && ( [5]에서 설정한 victim의 size == victim과 인접한 바로 다음 청크의 size )일 경우, if문이 충족되어 victim = victim -> fd가 된다.
[7] [5]에서 while문을 돌 때, victim의 size >= nb이므로 victim을 쪼개서 사용한다.
"remainder_size = victim의 size - 할당 요청된 size"로 설정한다.
[8] unlink()를 통해 victim의 이전 청크와 이후 청크를 연결하여, 현재 large bin의 linked list 구조를 유지해준다.
/* Exhaust */
if (remainder_size < MINSIZE)
{
set_inuse_bit_at_offset (victim, size);
if (av != &main_arena)
victim->size |= NON_MAIN_ARENA;
}[9] [7]에서 설정한 remainder_size < MINSIZE라면 if문을 충족한다
[10] set_inuse_bit_at_offset (victim, size)를 통해 victim의 인접한 다음 청크의 PREV_INUSE 플래그를 설정해준다.
[11] 현재 할당해줄 청크가 main_arena의 청크가 아니라면 victim의 NON_MAIN_ARENA 플래그를 설정해준다.
else
{
remainder = chunk_at_offset (victim, nb);
/* We cannot assume the unsorted list is empty and therefore
have to perform a complete insert here. */
bck = unsorted_chunks (av);
fwd = bck->fd;
if (__glibc_unlikely (fwd->bk != bck))
{
errstr = "malloc(): corrupted unsorted chunks";
goto errout;
}
remainder->bk = bck;
remainder->fd = fwd;
bck->fd = remainder;
fwd->bk = remainder;
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);
}[12] remainder_size가 MINSIZE보다 크다면, else문이 실행된다.
[13] remainder = victim에서 nb(할당 요청이 들어온 size)만큼 떨어진 곳의 청크로 설정해준다.
[14] bck = unsorted bin의 주소,
fwd = bck->fd(unsorted bin에 있는 첫 번째 청크)로 설정한다.
glibc_unlikely()에 관해서는 이후 글에서 따로 설명하도록 하겠다
[15] remainder->bk = bck(==unsorted bin의 주소),
remainder->fd = fwd(== 현재 unsorted bin에 있는 첫 번째 청크)로 설정한다.
[16] bck->fd = remainder,
fwd->bk = remainder로 설정한다. [15]~[16]을 통해 unsorted bin의 circular doubly linked list 구조를 유지한다
[17] remainder_size가 large bin에 속하는 크기라면, large bin에서만 쓰이는 fd_nextsize와 bk_nextsize를 NULL로 세팅해준다.
[18] 이후 set_head와 set_foot을 통해
현재 할당해줄 청크의 size와 PREV_INUSE, NON_MAIN_ARENA 플래그들을 설정해주고,
remainder의 size와 PREV_INUSE 플래그를 설정하고,
remainder와 인접한 다음 청크의 prev_size를 설정해준다.
**이로써, large bin의 청크가 분할되어 할당될 때 remainder는 MINSIZE보다 큰 크기를 가진다면 unsorted bin으로 분류됨을 알 수 있다.**
check_malloced_chunk (av, victim, nb);
void *p = chunk2mem (victim);
alloc_perturb (p, bytes);
return p;
}
}[19] 그 후 현재 할당해줄 청크를 "freed 청크 -> malloced 청크"로 정리해주고
할당해주려던 청크를 반환해준다.
'DreamHack: System Hacking > Heap Allocator Exploit(ptmalloc2)' 카테고리의 다른 글
| __builtin_expect() ( __glibc_unlikely(), __glibc_likely() ) (0) | 2023.08.29 |
|---|