Overview
본 게시글은 Daily Heap #6 게시글에서 이어지는 내용을 기술하고 있습니다.
malloc() in glibc 2.23
_int_malloc()
Fastbin size check
다음으로 실행되는 동작은 요청된 size를 만족할 수 있는 '재사용 가능한 chunk' 가 있는지 확인합니다. glibc 2.23을 기준으로 Fastbin, Smallbin, Largebin, Unsorted bin 총 4개의 bin을 사용하여 해제된 chunk를 관리하며 검사 순서는 Fastbin -> Smallbin -> Largebin 으로 동작합니다.
3362 /*
3363 If the size qualifies as a fastbin, first check corresponding bin.
3364 This code is safe to execute even if av is not yet initialized, so we
3365 can try it without checking, which saves some time on this fast path.
3366 */
3367
3368 if ((unsigned long) (nb) <= (unsigned long) (get_max_fast ()))
3369 {
3370 idx = fastbin_index (nb);
3371 mfastbinptr *fb = &fastbin (av, idx);
3372 mchunkptr pp = *fb;
3373 do
3374 {
3375 victim = pp;
3376 if (victim == NULL)
3377 break;
3378 }
3379 while ((pp = catomic_compare_and_exchange_val_acq (fb, victim->fd, victim))
3380 != victim);
3381 if (victim != 0)
3382 {
3383 if (__builtin_expect (fastbin_index (chunksize (victim)) != idx, 0))
3384 {
3385 errstr = "malloc(): memory corruption (fast)";
3386 errout:
3387 malloc_printerr (check_action, errstr, chunk2mem (victim), av);
3388 return NULL;
3389 }
3390 check_remalloced_chunk (av, victim, nb);
3391 void *p = chunk2mem (victim);
3392 alloc_perturb (p, bytes);
3393 return p;
3394 }
3395 }if 문에서 비교 대상인 (unsigned long)(nb) 값의 경우 이전 과정에서 checked_request2size() 호출을 통해 요청된 size에 overhead 값과 정렬을 끝낸 값이 저장되어 있습니다.
get_max_fast() 의 경우 아래와 같이 구현되어 'global_max_fast' 값으로 정의되어 있으며 해당 값은 set_max_fast() 매크로에 의해 정의되는 점을 확인할 수 있었습니다.
#define set_max_fast(s) \
global_max_fast = (((s) == 0) \
? SMALLBIN_WIDTH : ((s + SIZE_SZ) & ~MALLOC_ALIGN_MASK))
#define get_max_fast() global_max_fast이를 종합하면 요청된 size가 fastbin 범위에 해당될 경우 이를 탐색하는 과정이 수행되었습니다. 만약 fastbin 범위에 해당될 경우 chunk size가 포함될 수 있는 fastbin의 index를 획득합니다. 이는 fastbin_index(nb) 매크로를 통해 진행됩니다.
typedef struct malloc_chunk *mfastbinptr;
#define fastbin(ar_ptr, idx) ((ar_ptr)->fastbinsY[idx])mfastbinptr type의 경우 malloc_chunk 구조체를 참조하였으며 fastbin() 매크로는 인자로 전달받은 ar_ptr 구조체 중 "fastbinsY" 항목을 참조하였습니다. 마찬가지로 ar_ptr 구조체는 malloc_state 구조체를 참조하기 때문에 최종적으로 malloc_state -> fastbinsY[idx] 형식과 같은 결과를 얻을 수 있었습니다.
"fastbinsY" 는 fastbin을 관리하기 위해 배열로 선언된 요소로 fastbin size에 해당되는 chunk가 해제되었을 때 이곳에 기록하여 linked list로 관리합니다.
do ~ while()
다음으로 수행되는 `do ~ while()` 문을 이해하기 위해서는 fastbin에 대한 이해가 필요합니다. Fastbin은 LIFO 방식의 single linked list로 관리됩니다. 즉, chunk의 재할당을 위해 가장 최근에 해제된 항목을 반환하게 됩니다. 또한 single linked list로 구현되어 있기 때문에 malloc_chunk 구조체의 'fd' 만을 사용합니다.
아래 예시를 통해 몇 가지 핵심 내용을 짚어보았습니다.
```c
#include <stdlib.h>
int main(){
char *ptr1;
char *ptr2;
ptr1 = (char *)malloc(0x10);
ptr2 = (char *)malloc(0x10);
malloc(0x20); // dummy
free(ptr1);
free(ptr2);
return 0;
}먼저 ptr1을 해제한 뒤의 fastbin의 상태입니다.
gdb-peda$ heapinfo
(0x20) fastbin[0]: 0x944000 --> 0x0
(0x30) fastbin[1]: 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: 0x944070 (size : 0x20f90)
last_remainder: 0x0 (size : 0x0)
unsortbin: 0x0Overhead를 포함하여 0x20 size에 해당되기에 fastbin[0] index에 ptr1 chunk의 주소가 기록되어 있는 것을 확인할 수 있습니다.
gdb-peda$ heapinfo
(0x20) fastbin[0]: 0x944020 --> 0x944000 --> 0x0
(0x30) fastbin[1]: 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: 0x944070 (size : 0x20f90)
last_remainder: 0x0 (size : 0x0)
unsortbin: 0x0다음은 ptr2를 해제한 뒤의 fastbin 모습입니다. ptr2의 chunk 주소가 맨 앞으로 왔으며 linked list 형식으로 가리키고 있는 점을 확인할 수 있습니다.
이때 ptr1과 ptr2의 fd 값을 확인하면 각각 0x0과 0x944000 임을 확인할 수 있습니다. ptr2의 fd에는 ptr1의 주소가 기록 되었지만 가장 먼저 해제된 ptr1은 그렇지 않음을 확인할 수 있습니다.
이는 실제 fastbinsY 배열에 기록되어 있는 값을 보면 의문을 해결할 수 있습니다.
gdb-peda$ p main_arena
$1 = {
mutex = 0x0,
flags = 0x0,
fastbinsY = {0x209d020, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0}, 위에서 확인한 결과들의 경우 plugin을 통해 이해하기 쉽게 표현되어 있지만 실제 기록되어 있는 값은 가장 최근에 해제된 chunk의 주소가 기록되어 있습니다.
기술한 내용을 생각하며 do ~ while() 문의 설명을 진행하면 다음과 같습니다.
do{} 의 동작은 'pp' 변수에 저장되어 있는 값을 'victim' 변수에 저장하고 'victim'의 값이 NULL 일 경우 break 를 통해 중단합니다. 처음 동작을 시작할 때 'pp' 변수의 값은 가장 최근에 해제된 fastbin size chunk의 주소를 갖고 있습니다.
while() 문의 조건을 이해하기 위해서는 먼저 catomic_compare_and_exchange_val_acq() 매크로의 문법을 이해할 필요가 있었습니다. 해당 매크로는 'include/atomic.h' 파일에서 찾을 수 있었으며 코드는 아래와 같습니다.
/* Atomically store NEWVAL in *MEM if *MEM is equal to OLDVAL.
Return the old *MEM value. */
#if !defined atomic_compare_and_exchange_val_acq \
&& defined __arch_compare_and_exchange_val_32_acq
# define atomic_compare_and_exchange_val_acq(mem, newval, oldval) \
__atomic_val_bysize (__arch_compare_and_exchange_val,acq, \
mem, newval, oldval)
#endif
#ifndef catomic_compare_and_exchange_val_acq
# ifdef __arch_c_compare_and_exchange_val_32_acq
# define catomic_compare_and_exchange_val_acq(mem, newval, oldval) \
__atomic_val_bysize (__arch_c_compare_and_exchange_val,acq, \
mem, newval, oldval)
# else
# define catomic_compare_and_exchange_val_acq(mem, newval, oldval) \
atomic_compare_and_exchange_val_acq (mem, newval, oldval)
# endif
#endif사전에 정의되어 있는 내용 여부에 따라 다양한 정의 방식이 존재하였으며 동작 방식의 경우 주석문에서 확인할 수 있었습니다. mem 인자가 가리키는 곳의 값과 oldval의 값이 같을 경우 이를 newval의 값으로 변경하는 동작을 수행하였습니다.
조건을 분석해보면 fastbin에 존재하는 값이 'victim' 값과 동일할 경우 fastbin의 값을 'victim -> fd' 값으로 변경합니다. do{} 동작 중 'victim'의 값을 'pp'의 값으로 지정하였기 때문에 이는 참이되고 결과적으로 stack에서 pop을 하듯 다음 free chunk를 fastbin으로 이동하는 과정으로 해석할 수 있습니다.
Free chunk size check
위 과정이 정상적으로 수행되어 free chunk를 받아왔을 경우 해당 주소는 'victim' 변수에 기록되어 있습니다. 다음으로 진행하게 되는 코드의 경우 'victim' 값이 0이 아닐 경우에 아래 내용을 수행합니다.
Free chunk를 재할당하기 이전에 한 가지 조건문을 통한 검사를 진행하게 됩니다. 조건은 다음과 같습니다.
if (__builtin_expect (fastbin_index (chunksize (victim)) != idx, 0))
먼저 victim chunk의 size를 가져온 뒤 해당 size가 fastbin index에 해당되는지 확인합니다. 만약 fastbin index의 범위에 포함되지 않을 경우 "malloc(): memory corruption (fast)" error 문구를 출력하며 종료됩니다.
이와 같은 검사는 fd가 변조되어 의도되지 않은 공간에 chunk 할당을 시도할 때 예방할 수 있는 수단이 됩니다. 물론 이러한 검사 과정을 속이기 위해 기존 chunk와 같은 형태인 'fake chunk' 를 구성하여 우회하는 것이 가능합니다.
Allocate Chunk
모든 과정을 통과할 경우 fastbin에서 해당되는 chunk를 가져온 뒤 아래 코드를 수행한 뒤 반환합니다.
3390 check_remalloced_chunk (av, victim, nb);
3391 void *p = chunk2mem (victim);
3392 alloc_perturb (p, bytes);
3393 return p;check_remalloced_chunk() 매크로의 경우 다시 do_check_remalloced_chunk() 함수를 호출하며 이는 flag bit, alignment 등 사항에 대해 검사를 수행하게 됩니다.
malloc()을 통해 할당하게 될 경우 실제로 반환하게 되는 주소는 mem 영역인데 이를 chunk2mem() 매크로를 통해 주소값을 변경하는 과정을 거치게 됩니다.
마지막으로 alloc_perturb() 호출하는데 이 함수는 다음과 같이 구현되어 있습니다.
static int perturb_byte;
static void
alloc_perturb (char *p, size_t n)
{
if (__glibc_unlikely (perturb_byte))
memset (p, perturb_byte ^ 0xff, n);
}mem 영역에 대해 memset() 함수를 호출하여 perturb_byte ^ 0xff 값으로 초기화하는데 이 값에 대해 선언만 존재할 뿐 별도로 값을 지정하는 과정이 존재하지 않습니다. 한 가지 확실한 점은 malloc()을 통해 chunk를 할당하게 될 경우에는 이전 값에 대한 초기화가 진행되지 않는다는 점입니다.
마지막으로 mem 영역의 주소값을 가지고 있는 p 값을 반환하며 종료됩니다.
Reference
