_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 */
size = chunksize (p);mstate형 av와 mchunkptr형 p를 입력받는다. _int_free를 호출하는 __libc_free함수를 살펴보면, p는 할당 해제할 청크를 가리키는 포인터이며 av는 p가 속하는 arena이다.
다음으로 함수 내부에서 필요한 각종 변수들을 선언하는데, 이 중 size는 해제할 청크의 크기를 가리킨다. 그 외 다른 변수들은 필요할 때 알아보도록 하자.
/* Little security check which won't hurt performance: the
allocator never wrapps around at the end of the address space.
Therefore we can exclude some size values which might appear
here by accident or by "design" from some intruder. */
if (__builtin_expect ((uintptr_t) p > (uintptr_t) -size, 0)
|| __builtin_expect (misaligned_chunk (p), 0))
malloc_printerr ("free(): invalid pointer");
/* We know that each chunk is at least MINSIZE bytes in size or a
multiple of MALLOC_ALIGNMENT. */
if (__glibc_unlikely (size < MINSIZE || !aligned_OK (size)))
malloc_printerr ("free(): invalid size");
check_inuse_chunk(av, p);그리고 몇 가지 사전적인 보호 절차가 이루어진다.
free할 청크에 대해 유효한 포인터인지, size값이 유효한 지, 제대로 된 청크인지 등을 확인한다.
#if USE_TCACHE
{
size_t tc_idx = csize2tidx (size);
if (tcache != NULL && tc_idx < mp_.tcache_bins)
{
/* Check to see if it's already in the tcache. */
tcache_entry *e = (tcache_entry *) chunk2mem (p);
/* This test succeeds on double free. However, we don't 100%
trust it (it also matches random payload data at a 1 in
2^<size_t> chance), so verify it's not an unlikely
coincidence before aborting. */
if (__glibc_unlikely (e->key == tcache_key))
{
tcache_entry *tmp;
size_t cnt = 0;
LIBC_PROBE (memory_tcache_double_free, 2, e, tc_idx);
for (tmp = tcache->entries[tc_idx];
tmp;
tmp = REVEAL_PTR (tmp->next), ++cnt)
{
if (cnt >= mp_.tcache_count)
malloc_printerr ("free(): too many chunks detected in tcache");
if (__glibc_unlikely (!aligned_OK (tmp)))
malloc_printerr ("free(): unaligned chunk detected in tcache 2");
if (tmp == e)
malloc_printerr ("free(): double free detected in tcache 2");
/* If we get here, it was a coincidence. We've wasted a
few cycles, but don't abort. */
}
}
if (tcache->counts[tc_idx] < mp_.tcache_count)
{
tcache_put (p, tc_idx);
return;
}
}
}
#endif다음 부분은 tcache를 사용하는 경우에 동작하는 코드이다.
해제할 청크를 tcache_entry형 포인터 e로 변환해 (tcache의 청크에 해당하는 구조체) 해당 청크에 대해 double free여부를 검사한다.
우선 e의 key값이 tcache_key와 동일하다면 if문이 실행된다. (=각종 검사의 대상이 된다)
if문 내부로 들어가면 현재 free할 청크의 size에 해당하는 index의 entries 연결리스트의 가장 첫 번째 청크부터 마지막 청크까지를 반복문에 의해 모두 검사한다.
초기값 0에서부터 반복 시 마다 1씩 증가하는 값인 cnt를 가지고 mp_.tcache_count의 값과 비교해 청크 개수가 올바른지 확인하고 aligned_OK 매크로를 사용하여 연결리스트에 존재하는 청크의 align이 올바른지 확인한다. (주소값의 16진수 기준 마지막 자리수가 0x0인지 확인함) 그리고 tmp==e의 여부를 확인하여 free하려는 청크가 이미 tcache에 들어있는지를 확인한다.
모든 경우에 대해 위의 검사를 통과했다면 해당 size의 tcache에 아직 자리가 있다면 tcache_put함수에 의해 해제할 청크가 tcache에 들어가게 되고 return에 의해 _int_free가 종료된다.
만약 tcache가 가득찼다면 여기서 free가 이루어지지 못하고 다음 코드의 진행이 계속된다.
간단하게 다음 코드의 진행을 살펴보면 크게 if문, else if문, else문으로 나눌 수 있다.
우선 아래 코드에서 이 큰 구조에 해당하는 조건들은 볼드 처리를 해주었다.
간단하게 미리 언급하면 다음과 같다.
if ⇒ fastbin에 들어갈 수 있는 경우
else if ⇒ fastbin 이외의 경우이면서 mmap에 의해 할당받지 않은 경우
else ⇒ mmap에 의한 할당인 경우 (munmap으로 해제)
1. if문
우선 가장 첫 번째 if문을 살펴보자.
/*
If eligible, place chunk on a fastbin so it can be found
and used quickly in malloc.
*/
**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 (chunksize_nomask (chunk_at_offset (p, size))
<= CHUNK_HDR_SZ, 0)
|| __builtin_expect (chunksize (chunk_at_offset (p, size))
>= av->system_mem, 0))
{
bool fail = true;
/* We might not have a lock at this point and concurrent modifications
of system_mem might result in a false positive. Redo the test after
getting the lock. */
if (!have_lock)
{
__libc_lock_lock (av->mutex);
fail = (chunksize_nomask (chunk_at_offset (p, size)) <= CHUNK_HDR_SZ
|| chunksize (chunk_at_offset (p, size)) >= av->system_mem);
__libc_lock_unlock (av->mutex);
}
if (fail)
malloc_printerr ("free(): invalid next size (fast)");
}
해당 if문에서 size의 값이 fastbin의 범위에 들어가는지를 확인하고 있는 것으로 보아 이 조건문 내부에서는 fastbin에 넣는 free가 실행될 것임을 생각해볼 수 있다.
추가적으로 TRIM_FASTBINS가 설정되어있다면 추가적인 검증조건이 존재한다. 초기값은 0인 것 같은데 어떤 경우에 1이 되는지는 잘 모르겠다.
계속 살펴보자.
__builtin_expect (chunksize_nomask (chunk_at_offset (p, size)) <= CHUNK_HDR_SZ, 0) || __builtin_expect (chunksize (chunk_at_offset (p, size)) >= av->system_mem, 0) 가 참이라면 fail은 true가 되고 fail이 true라면 "free(): invalid next size (fast)"가 출력되며 에러가 날 것이다.
따라서 이 조건문은 청크의 next size를 검증하는 것 같다.
좀 더 자세히 살펴보면 ||(or)로 연결되어 있는 두 조건 중 첫 번째는 해제할 청크의 다음 청크의 사이즈가 헤더의 크기, 즉 0x10보다 작지는 않은지를 검사하며 두 번째 조건은 다음 청크의 사이즈가 해제할 청크가 속하는 arena의 system_mem값보다 크지는 않은지를 검사한다. (system_mem은 해당 arena에서 시스템에 의해 할당 받은 메모리의 전체 크기를 의미한다).
두 조건 중 하나에 해당된다면 뭔가 잘못된 사이즈 값을 갖고 있는 것이므로 에러를 발생시키는 것임을 알 수 있고, fastbin의 경우에는 다음 청크의 size값까지 검증 대상에 들어가고 있음을 알 수 있다. 확실히 tcache보다는 뭔가 보호기법들이 빡센 느낌이다.
free_perturb (chunk2mem(p), size - CHUNK_HDR_SZ);
atomic_store_relaxed (&av->have_fastchunks, true);
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;위의 조건들을 무사히 통과했다면 실행되는 부분들이다.
해제할 청크를 perturb_byte가 0이 아니라면 perturb_byte로 헤더를 제외한 모든 영역을 채워준다.
그리고 p가 속한 arena의 have_fastchunks값을 true로 바꾸어준다. malloc_state 구조체에서 fastbin chunks가 최근에 free blocks에 추가되었다면 set되는 값이다.
그리고 맨 처음에 mfastbinptr *fb; 과 같이 선언되었던 변수 fb에 현재 해제할 청크에 해당하는 idx의 fastbin리스트의 주소를 대입한다. (fastbin(av, idx)는 매크로로 av→fastbinsY[idx]와 동일하다.)
다음으로는 old에 *fb를 대입하는데, 이 과정에서는 mchunkptr형 변수 old가 현재 다루고 있는 fastbin리스트에 가장 마지막으로 들어간 청크를 가리키게 될 것이다.
if (SINGLE_THREAD_P)
{
/* 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))
malloc_printerr ("double free or corruption (fasttop)");
p->fd = PROTECT_PTR (&p->fd, old);
*fb = p;
}
else
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))
malloc_printerr ("double free or corruption (fasttop)");
old2 = old;
p->fd = PROTECT_PTR (&p->fd, old);
}
while ((old = catomic_compare_and_exchange_val_rel (fb, p, old2))
!= old2);
그리고 싱글 스레드인지의 여부에 따라 두 가지로 나뉘어 실행된다.
만약 싱글 스레드라면 다음과 같다.
우선 old==p의 여부를 확인하여 가장 최근에 fastbin에 들어간 청크와 현재 해제할 청크가 동일하다면 double free를 감지하여 오류를 발생시킨다. 이 조건문은 fastbin dup을 공부할 때 많이 보던 부분이다. 그리고 이 조건을 통과하면 p의 fd에 old의 값을 대입하고 *fb에 p를 대입한다. 즉, fastbin에 현재 free할 청크를 추가한다.
만약 싱글 쓰레드가 아니라면 (old = catomic_compare_and_exchange_val_rel (fb, p, old2)) != old2 가 참이 아닐때까지 특정 과정을 반복한다.
반복문 내부는 다음과 같다.
우선 old==p의 여부를 검사해 double free여부를 검사한 다음, p의 fd값을 old로 바꾸어준다. 여기서는 old2라는 변수가 하나 더 사용되는데 정확한 매커니즘은 잘 모르겠지만 단일 스레드가 아닌 상황에서의 fastbin 리스트에 청크를 추가하는 과정이 이루어지는 듯 하다.
/* 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
allocated again. */
if (have_lock && old != NULL
&& __builtin_expect (fastbin_index (chunksize (old)) != idx, 0))
malloc_printerr ("invalid fastbin entry (free)");
}fastbin에 해당하는 경우의 마지막 보호기법이다. fastbin poisoning을 공부할 때 우회해야 할 보호기법으로 많이 보던 조건과 형태가 매우 유사하다. 우선 have_lock이 0이 아니면서 old가 널이 아닐 때에 한하여 __builtin_expect (fastbin_index (chunksize (old)) != idx 라는 조건을 검사하게 된다. 이 조건이 의미하고 있는 바는 old의 chunksize에 해당하는 인덱스의 값이 현재 우리가 청크를 추가하고 있는 리스트의 인덱스 값과 같은지의 여부를 판단하는 것이다. 그런데 애초에 idx의 값이 할당할 청크의 size로부터 가져와지는 점, 그리고 우리가 청크를 넣을 bin이 idx값을 바탕으로 선택되는 점을 고려하면 이 보호기법에 걸리는 상황은 흔하지는 않을 듯 하다.
어쨌든 위 보호기법을 마지막으로 fasbin에 들어가는 경우의 free가 마무리되었다.
만약 fastbin에 해당하는 경우라면 여기서 free가 종료될 것이다.
2. else if문
여기서 부터는 fastbin이 아닌 다른 경우+mmap으로 할당받지 않은 경우의 free가 진행될 것이다. 맨위의 주석을 보면 consolidate과정도 함께 일어나는 듯 하다.
/*
Consolidate other non-mmapped chunks as they arrive.
*/
**else if (!chunk_is_mmapped(p))** {
/* If we're single-threaded, don't lock the arena. */
if (SINGLE_THREAD_P)
have_lock = true;
if (!have_lock)
__libc_lock_lock (av->mutex);
nextchunk = chunk_at_offset(p, size);
/* Lightweight tests: check whether the block is already the
top block. */
if (__glibc_unlikely (p == av->top))
malloc_printerr ("double free or corruption (top)");
/* Or whether the next chunk is beyond the boundaries of the arena. */
if (__builtin_expect (contiguous (av)
&& (char *) nextchunk
>= ((char *) av->top + chunksize(av->top)), 0))
malloc_printerr ("double free or corruption (out)");
/* Or whether the block is actually not marked used. */
if (__glibc_unlikely (!prev_inuse(nextchunk)))
malloc_printerr ("double free or corruption (!prev)");
nextsize = chunksize(nextchunk);
if (__builtin_expect (chunksize_nomask (nextchunk) <= CHUNK_HDR_SZ, 0)
|| __builtin_expect (nextsize >= av->system_mem, 0))
malloc_printerr ("free(): invalid next size (normal)");
free_perturb (chunk2mem(p), size - CHUNK_HDR_SZ);
만약 싱글 스레드라면 have_lock을 true로 바꾼다.
그리고 have_lock의 값이 0이라면 (아마도 싱글스레드가 아니라면) 해당하는 아레나의 mutex값을 가지고 락을 건다. 잘은 모르지만 뮤텍스같은건 멀티 스레드 상황에서 레이스 컨디션을 방지하기 위한 조치로 알고 있기 때문에 뭔가 내가 알고 있는 지식들과 일맥상통하는 듯 하다. 내가 추상적으로 알고있던 지식들이 코드로 구현, 제어되고 있는 것을 보는 것 같아서 조금 흥미로웠다.
청크를 가리키는 포인터변수 nextchunk에 p의 바로 다음에 위치하는 청크의 주소(p의 주소+p의 size값에 해당)를 대입한다. (확실하진 않지만 병합을 위해 필요할 것 같은 느낌이다.)
+이건 backward병합까지 본 다음 생각난 사실인데, 한 청크 내부에서는 이전 청크의 size나 사용 여부와 같은 정보는 존재하지만 다음 청크의 정보는 담고 있지 않기 때문에 따로 next와 관련된 변수들을 선언하여 관리하는 듯 하다. 다음 청크로의 접근은 현재 청크의 주소에 size만큼의 offset을 더한 주소로 이루어진다.
다음으로는 세 가지 검사 과정을 거친다. 오류 메시지를 보면 double free나 corruption을 감지하는 듯 하다.
우선 첫 번째로는 p가 top block인지를 확인하고 두 번째로는 nextchunk가 top chunk의 베이스 주소+topchunk의 size보다 큰 지의 여부, 즉 현재 아레나에 할당된 메모리 영역 내부에 있는지를 확인한다. 마지막으로는 next_chunk의 prev_inuse flag가 set되어있는지를 확인한다. prev_inuse는 직전 청크가 사용중인지를 나타내므로 현재 free할 청크가 in-use가 아니라면 오류가 발생하게 된다.
그리고 nextsize라는 값에 nextchunk의 size값을 대입하고, 또 다시 검증을 거친다.
이번에는 nextchunk의 사이즈가 헤더의 크기 0x10보다 작지는 않은지, system_mem값보다 크지는 않은지를 검사한다.
여기까지만 봐도 뭔가 arena영역에서의 청크 조작은 매우 까다로울 것이라는 것을 알 수 있다. 왜 힙 익스에서 tcache가 주요 공격 대상이 되는지 이해가 된다.
/* consolidate backward */
if (!prev_inuse(p)) {
prevsize = prev_size (p);
size += prevsize;
p = chunk_at_offset(p, -((long) prevsize));
if (__glibc_unlikely (chunksize(p) != prevsize))
malloc_printerr ("corrupted size vs. prev_size while consolidating");
unlink_chunk (av, p);
}이제 병합 과정이 이루어지는 듯 하다. 먼저 backward로의 병합이 이루어진다.
만약 p의 prev_inuse가 0이라면, 즉 p의 직전 청크가 사용중이 아니라면 이는 곧 병합의 대상이라는 의미이기 때문에 조건문 내부로 들어가서 직전 청크와 p의 병합이 이루어진다.
우선 size에 prevsize의 값을 더해 사이즈를 이전 청크+현재 청크로 늘려준다.
그리고 현재 청크의 주소를 담고 있는 p에는 이전 청크의 size만큼 값을 빼주어 p가 이전 청크를 가리키도록 만든다.
그리고 이전 청크의 주소로 바뀐 p가 가리키는 size값과 prevsize값의 일치 여부를 검사한다.
이후 unlink_chunk로 arena로부터 p를 unlink한다.
if (nextchunk != av->top) {
/* get and clear inuse bit */
nextinuse = inuse_bit_at_offset(nextchunk, nextsize);
/* consolidate forward */
if (!nextinuse) {
unlink_chunk (av, nextchunk);
size += nextsize;
} else
clear_inuse_bit_at_offset(nextchunk, 0);
그리고 nextchunk가 top block에 해당되지 않는다면 nextchunk의 직후에 위치하는 청크의 prev_inuse flag값을 가져와 nextchunk가 사용중인지를 확인한다. 만약 사용중이 아니라면 nextchunk까지도 arena에서 unlink하고 size에는 nextsize값을 더해준다.
따라서 만약 해제하려는 청크의 앞뒤 청크가 모두 해제 상태라면 p는 직전 청크의 주소를 가리키며 size는 직전 청크+현재청크+직후청크의 사이즈값이 될 것이다.
만약 nextchunk가 사용중이었다면 nextchunk의 prev_inuse flag를 해제하여 이전 청크가 해제되었다는 것을 표시해준다.
/*
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))
malloc_printerr ("free(): corrupted unsorted chunks");
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);
}이제 병합을 완료한 p를 unsorted bin에 넣어줄 차례인 것 같다.
해제된 청크는 tcache, fastbin에 들어가지 않으면 일단 무조건 unsorted bin에 들어간다고 배운 것과 동일하다.
arena로부터 unsorted bin의 값을 가져온다. 여기서 한 번 검증을 거치는데, fwd → bk의 값과 bck가 같지 않으면 오류가 발생하는데 매커니즘을 보면 원래 unsorted bin에서 fwd와 bck는 연결되어있던 관계이다. 그런데 fwd의 bk와 bck가 같지 않다면 청크의 corruption이 일어난 것이므로 오류를 발생시키는 것이다.
이 검증을 통과하고 나면 p의 fd값을 fwd로, p의 bk값을 bck로 만들어 p를 unsorted bin에 삽입한다. 그리고 bck의 fd값과 fwd의 bk값도 p로 바꾸어준다.
그리고 헤더의 size값과 다음 청크의 prev_size값을 size값이 되도록 만들어준다.
그리고 해제된 청크의 값들이 제대로 설정되었는지 확인해준다.
/*
If the chunk borders the current high end of memory,
consolidate into top
*/
else {
size += nextsize;
set_head(p, size | PREV_INUSE);
av->top = p;
check_chunk(av, p);
}이는 이전 if문중 next chunk가 top chunk인지 확인하는 조건의 else문인데, nextchunk가 top chunk에 해당하는 경우이다. 이 경우에는 top chunk에 현재 청크를 병합해준다.
/*
If freeing a large space, consolidate possibly-surrounding
chunks. Then, if the total unused topmost memory exceeds trim
threshold, ask malloc_trim to reduce top.
Unless max_fast is 0, we don't know if there are fastbins
bordering top, so we cannot tell for sure whether threshold
has been reached unless fastbins are consolidated. But we
don't want to consolidate on each free. As a compromise,
consolidation is performed if FASTBIN_CONSOLIDATION_THRESHOLD
is reached.
*/
if ((unsigned long)(size) >= FASTBIN_CONSOLIDATION_THRESHOLD) {
if (atomic_load_relaxed (&av->have_fastchunks))
malloc_consolidate(av);
if (av == &main_arena) {
#ifndef MORECORE_CANNOT_TRIM
if ((unsigned long)(chunksize(av->top)) >=
(unsigned long)(mp_.trim_threshold))
systrim(mp_.top_pad, av);
#endif
} else {
/* Always try heap_trim(), even if the top chunk is not
large, because the corresponding heap might go away. */
heap_info *heap = heap_for_ptr(top(av));
assert(heap->ar_ptr == av);
heap_trim(heap, mp_.top_pad);
}
}
if (!have_lock)
__libc_lock_unlock (av->mutex);
}주석을 보면 fastbin의 consolidation과 관련한 부분인 것을 알 수 있다. 효율성을 위해 모든 경우에 실행하기 보다는 특정 조건을 만족하면 (threshold를 넘으면) 시행하는 것으로 보이는데, 여기선 size의 값이 FASTBIN_CONSOLIDATION_THRESHOLD(=0x10000) 이상일 경우, 그리고 av→have_fastchunks가 참일 경우 malloc_consolidate(av); 가 수행된다.
그리고 av가 main_arena인지 아닌지의 여부에 따라 각각 상황에 맞게 힙 영역을 trim한다. 아마 가장 top영역에서 사용되지 않는 크기가 너무 클 경우에 top을 줄이는 과정인 듯 하다.
그리고 lock을 해제하며 두 번째 경우에 해당하는 free가 종료된다.
3. else문
/*
If the chunk was allocated via mmap, release via munmap().
*/
**else** {
munmap_chunk (p);
}
}마지막 경우는 free할 대상이 mmap을 통해 할당받은 경우이다. 이 경우에는 주석에 나와있는대로 munmap을 통해 해제해준다.
<결론>
free과정은 tcache ⇒ fastbin ⇒ 그 외 ⇒ mmaped chunk의 순으로 이루어진다. 확실히 여러 검증 절차를 살펴보면 tcache ⇒ fastbin ⇒ 그 외의 순서로 보호 기법이 더 빡세진다는 것을 알 수 있다. 확실히 tcache가 뭔가 조작하기에는 가장 쉬울 것이라는 것을 충분히 느낄 수 있었다.
