이전에 개인적으로 libc_malloc을 살펴본 적이 있는데, libc_malloc 내부에서 _int_malloc의 호출이 이루어졌었다. 그때 분석한 바로는 tache bin에 있는 청크의 재할당은 libc_malloc에서 이루어졌었고 그 외의 상황에서는 _int_malloc을 호출하였던 것으로 기억하는데, 그래서 이후에 꼭 _int_malloc도 살펴봐야겠다고 생각했는데 이번 기회에 살펴보게 되었다. libc_malloc의 분석내용과 연결지으며 살펴봐야겠다.
현재 속하는 arena인 av와 할당할 크기인 bytes를 입력받고 할당된 주소값을 반환한다.
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 */
#if USE_TCACHE
size_t tcache_unsorted_count; /* count of unsorted chunks processed */
#endif그 외에도 여러 변수들을 선언하는데 추후에 필요할 때 언급할 예정이다.
/*
Convert request size to internal form by adding SIZE_SZ bytes
overhead plus possibly more to obtain necessary alignment and/or
to obtain a size of at least MINSIZE, the smallest allocatable
size. Also, checked_request2size returns false for request sizes
that are so large that they wrap around zero when padded and
aligned.
*/
nb = checked_request2size (bytes);
if (nb == 0)
{
__set_errno (ENOMEM);
return NULL;
}
/* There are no usable arenas. Fall back to sysmalloc to get a chunk from
mmap. */
if (__glibc_unlikely (av == NULL))
{
void *p = sysmalloc (nb, av);
if (p != NULL)
alloc_perturb (p, bytes);
return p;
}우선 할당을 원하는 크기인 bytes를 청크의 크기로 변환하여 nb에 저장한다.
만약 nb가 0이라면 null을 반환하고 malloc을 종료한다.
그리고 현재 arena를 의미하는 av가 널이라면, 즉 usable arenas가 없다면 sysmalloc을 호출하여 mmap으로부터 청크를 얻어 반환한다. (return p)
위의 두 가지 경우 중 어디에도 해당되지 않는다면 계속 코드를 진행한다.
밑부분을 간단하게 살펴보면, if문-if문-else 문으로 크게 나뉠 수 있는데 구조는 다음과 같다.
- if문 ⇒ fastbin 크기
- if문 ⇒smallbin 크기
- else문 ⇒ largebin 크기
이 구조를 기억하면서 코드를 살펴보자.
1. if문 ⇒ fastbin 크기
/*
If the size qualifies as a fastbin, first check corresponding bin.
This code is safe to execute even if av is not yet initialized, so we
can try it without checking, which saves some time on this fast path.
*/
if ((unsigned long) (nb) <= (unsigned long) (get_max_fast ()))
{
idx = fastbin_index (nb);
mfastbinptr *fb = &fastbin (av, idx);
mchunkptr pp;
victim = *fb;
if (victim != NULL)
{
if (__glibc_unlikely (misaligned_chunk (victim)))
malloc_printerr ("malloc(): unaligned fastbin chunk detected 2");
if (SINGLE_THREAD_P)
*fb = REVEAL_PTR (victim->fd);
else
REMOVE_FB (fb, pp, victim);
만약 nb가 fastbin범위에 든다면 if문의 내부로 들어간다. 주석을 읽어보면, fastbin범위의 할당이 요청되면 가장 먼저 fastbin을 확인한다는 의미인 듯 하다. 따라서 if문 내부에는 fastbin에 할당할 청크가 존재하는지 확인하는 코드가 실행될 것으로 예상해볼 수 있다.
nb값을 바탕으로 fastbin에 해당하는 index값을 가져오고 포인터 fb에 해당 인덱스의 fastbin리스트 주소를 가져오고, victim에 *fb, 즉 fastbin 리스트를 대입한다.
만약 victim이 널이 아니라면 여러 fastbin 검증을 거치게 된다.
우선 victim에 가져온 fastbin청크를 바탕으로 misaligned 여부를 판단한다. misaligned_chunk 매크로를 타고 들어가보면 인자의 주소값을 0b1111과 and 연산하여 0이 아니라면 misaligned로 판단하는 듯 하다. 즉, 주소값의 16진수 기준 마지막 자리수가 0이어야 제대로 align되어 있다고 판단하는 듯 하다.
다음으로는 싱글스레드의 여부를 확인하여 싱글스레드면 fb에 victim의 fd값을 넣어준다. (단, REVEAL_PTR 매크로로 safe linking 했던 것을 복구하여 대입한다.)
처음에는 이게 정확히 뭘 하는 건가 했는데 포인터변수인 fb에 fd를 넣어줌으로써 fastbin의 가장 첫 번째 청크를 fd로 바꾸어주는, 즉 맨 앞의 청크를 fastbin연결리스트에서 제거하는 행위인 것 같다.
싱글 스레드가 아니라면 REMOVE_FB라는 매크로를 통해 특정 작업을 한다. 아마 이전과 동일하게 fastbin 리스트에서 청크를 제거하는 행위일 듯 하다.
fastbin에서 청크를 언링크하는 것으로 보아, 동적할당을 통해 해당 청크(즉, victim)을 반환할 것으로 보인다.
if (__glibc_likely (victim != NULL))
{
size_t victim_idx = fastbin_index (chunksize (victim));
if (__builtin_expect (victim_idx != idx, 0))
malloc_printerr ("malloc(): memory corruption (fast)");
check_remalloced_chunk (av, victim, nb);
#if USE_TCACHE
(...중략...)
#endif
void *p = chunk2mem (victim);
alloc_perturb (p, bytes);
return p;
}
}
}그리고 또 한번의 검증 절차를 거치는데, 조건을 잘 보니 어디서 많이 보던 것이다.
바로 fastbin poisoning을 통해서 원하는 곳에 청크를 할당할 때, 그 주소의 이전 부분에 size를 알맞게 세팅해주어야 했던 우회기법을 만들어낸 검증 절차이다. victim의 주소로부터 가져온 인덱스값과 nb로부터 가져온 인덱스 값을 비교하여 내가 원하는 할당 크기가 victim의 주소에 알맞게 헤더로서 세팅되어있는지를 확인하고 있다.
그리고 나서 victim의 청크가 제대로된 청크인지 (arena일치, size가 범위 내에 있는 등등)을 check_remalloced_chunk 로 확인한다.
다음으로는 tcache를 사용할 때만 유효한 부분이 존재하는데, 일단은 뒷 부분 먼저 보고 이 부분을 살펴보기로 하자.
void형 포인터변수 p에 victim을 메모리로 변환하여 대입하고, 이를 반환하고 있다. 이전에 예측한대로, 만약 이 if문 내부에 들어왔다면 victim이 동적할당의 결과로 반환된다. 만약 fastbin크기의 동적할당요청이면서 fastbin내부에 청크가 존재했다면 그 청크가 반환되고 malloc은 종료될 것이다.
이제 잠깐 미뤄두었던 tcache관련 코드를 살펴보자.
#if USE_TCACHE
/* While we're here, if we see other chunks of the same size,
stash them in the tcache. */
size_t tc_idx = csize2tidx (nb);
if (tcache && tc_idx < mp_.tcache_bins)
{
mchunkptr tc_victim;
/* While bin not empty and tcache not full, copy chunks. */
while (tcache->counts[tc_idx] < mp_.tcache_count
&& (tc_victim = *fb) != NULL)
{
if (__glibc_unlikely (misaligned_chunk (tc_victim)))
malloc_printerr ("malloc(): unaligned fastbin chunk detected 3");
if (SINGLE_THREAD_P)
*fb = REVEAL_PTR (tc_victim->fd);
else
{
REMOVE_FB (fb, pp, tc_victim);
if (__glibc_unlikely (tc_victim == NULL))
break;
}
tcache_put (tc_victim, tc_idx);
}
}
#endif주석을 살펴보면 동일한 사이즈의 다른 청크들이 있다면 그것을 tcache에 넣는다고 한다.
정확히 뭘 하는건지 이해하기 힘드니 일단 코드를 계속 보자.
우선 nb에 해당하는 tcache 인덱스값을 가져오고, while문에 의해 특정 코드가 반복된다.
주석을 읽어보면 bin이 비거나 tcache가 가득차지 않는 한 chunks를 copy한다고 되어있는데(실제로 코드를 살펴보면, while문의 조건과 동일하다), 뭔가 tcache에 자리가 생겼다면 bin의 청크를 tcache로 옮기는 것 같은 느낌이다.
while문 내부 코드를 살펴보자.
tc_victim은 *fb를 초기값으로, 순차적으로 fastbin의 리스트에서 fd값을 통해 청크들을 가져와 대입되고 있다. 그리고 그 과정에서 tc_victim이 misaligned 여부를 검사하고, (애초에 반복이 된다는 것 자체만으로 tcache에 자리가 있음이 보장된다는 것을 기억해야 함) 검사를 통과하면 fastbin리스트에서 tc_victim을 unlink한 다음 (fastbin의 재할당과정과 동일하게 단일스레드라면 단순히 포인터변수의 대입을 이용, 다중 스레드라면 REMOVE_FB를 이용한다), tc_victim을 tcache_put 을 이용해 tcache에 넣어준다. 코드를 보니까 추측한 바가 맞는 듯 하다.
2. if문 ⇒smallbin 크기
/*
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)
{
bck = victim->bk;
if (__glibc_unlikely (bck->fd != victim))
malloc_printerr ("malloc(): smallbin double linked list corrupted");
set_inuse_bit_at_offset (victim, nb);
bin->bk = bck;
bck->fd = bin;
if (av != &main_arena)
set_non_main_arena (victim);
check_malloced_chunk (av, victim, nb);
#if USE_TCACHE
(...중략...)
#endif
void *p = chunk2mem (victim);
alloc_perturb (p, bytes);
return p;
}
}
이제부터는 nb가 fastbin의 범위에 들지 않는다면 실행되는 부분이다.
그 중에서도 smallbin크기에 속한다면 if문 내부로 들어간다.
주석을 읽어보면 이제 regular bin을 살펴볼 차례라고 하면서 large bin과 다르게 small bin은 빠른 편이라고 되어있는데, 실제로 ptmalloc에 대해 공부할 때 다른 크기의 요청은 fastbin → small bin→unsorted bin의 순서로 탐색하지만 large bin크기의 요청은 unsorted bin을 먼저 탐색하고 large bin을 탐색하며 탐색 과정에서 unsorted bin의 청크들이 원래 크기의 bin으로 분류되는 과정까지 진행된다고 했으므로 확실히 large bin 크기의 할당이 훨씬 복잡할 것 같은 느낌이다. 실제로 주석에서도 For a large request, we need to wait until unsorted chunks are processed to find best fit 라는 언급이 존재한다. 뭔가 large bin크기의 요청은 벌써부터 분석이 무서워진다.. 일단 small bin을 살펴보자…
만약 nb크기에 해당하는 smallbin인덱스의 bin값이 그 bin의 bk값과 동일하지 않다면 if문 내부로 들어간다. 이게 무슨 의미인지 고민을 해보았는데, smallbin에 청크가 존재하는지 아닌지의 여부를 판단하는 것인 것 같다. 만약 smallbin에 청크가 없다면 smallbin에 청크가 있을 때와 동일한 방법으로 할당이 어려운 것은 당연하다. 그래서 추후에 다른 방식으로 할당이 이루어질 것이다. 확실한 건 아니지만 추측하기로는 unsorted bin을 탐색한다던가 아예 새로운 영역을 할당한다거나 하는 코드로 이어지지 않을까?
어쨋든 small bin에 청크가 존재한다면 이제 그 청크를 unlink할 차례이다.
우선 victim은 bin의 bk인 상태이며, victim의 bk의 fd가 victim이 아니라면 오류를 발생시킨다.
보통 경우라면 당연히 통과하겠지만, 메모리 corruption을 하려는 사람의 입장에서는 매우 까다로운 조건이다. 애초에 bk나 fd의 변조자체를 막아버린 것이기 때문이다.
검증을 통과하고 나면 본격적인 unlink절차에 들어간다.
victim의 다음 청크의 prev_inuse flag를 set하고 연결리스트 상에서 청크 2개의 fd, bk를 서로 연결하여 victim을 연결리스트에서 제거한다.
이후 (tcache사용 시의 코드는 잠시 뒤에 보는 걸로 하고) victim의 메모리주소를 가져와 void형 포인터 p에 넣고 p를 반환한다.
따라서 smallbin에 알맞은 청크가 존재했다면 여기서 malloc이 종료될 것이다. 하지만 그러지 못했다면 코드는 계속 진행될 것이다.
#if USE_TCACHE
/* While we're here, if we see other chunks of the same size,
stash them in the tcache. */
size_t tc_idx = csize2tidx (nb);
if (tcache && tc_idx < mp_.tcache_bins)
{
mchunkptr tc_victim;
/* While bin not empty and tcache not full, copy chunks over. */
while (tcache->counts[tc_idx] < mp_.tcache_count
&& (tc_victim = last (bin)) != bin)
{
if (tc_victim != 0)
{
bck = tc_victim->bk;
set_inuse_bit_at_offset (tc_victim, nb);
if (av != &main_arena)
set_non_main_arena (tc_victim);
bin->bk = bck;
bck->fd = bin;
tcache_put (tc_victim, tc_idx);
}
}
}
#endif잠시 미뤄두었던 tcache관련 코드이다. 주석을 보니 이전에 fastbin에서 봤던 것과 동일하다. 아마 여기도 동일하게 tcache에 자리가 있거나 bin이 비지 않는한 bin의 청크를 tcache로 옮겨주는 과정인 듯 하다.
실제로 while문에서 그 여부를 검사하고 있고, while문이 돌아가는 한, bin에 존재하는 청크를 bin리스트에서 unlink하고 tcache_put을 통해 tcache에 넣어주고 있다.
3. else문 ⇒ largebin 크기
/*
If this is a large request, consolidate fastbins before continuing.
While it might look excessive to kill all fastbins before
even seeing if there is space available, this avoids
fragmentation problems normally associated with fastbins.
Also, in practice, programs tend to have runs of either small or
large requests, but less often mixtures, so consolidation is not
invoked all that often in most programs. And the programs that
it is called frequently in otherwise tend to fragment.
*/
else
{
idx = largebin_index (nb);
if (atomic_load_relaxed (&av->have_fastchunks))
malloc_consolidate (av);
}fastbin, smallbin 중 어느 크기에도 속하지 않는다면 해당 else문의 내부로 들어온다.
주석을 읽어보면 계속 진행하기 전에 fastbin을 병합한다고 한다. 그리고 지금 타이밍에 병합을 하는 것이 왜 효율적인지도 설명해주고 있다.
실제로 코드를 보면 fastbin에 청크가 있다면, malloc_consolidtate가 이루어진다. 여기까지 오고 나니 생각나는 것이 하나 있었다. 이전에 ptmalloc을 공부할 때 fastbin의 consolidation이 largebin크기의 청크가 할당되거나 small bin을 다 돌아도 청크를 찾지 못할 때 이루어진다고 했는데, 되게 상관없는 두 가지가 consolidation의 조건이라는 이름으로 묶여있다고 생각했는데, 이는 malloc_consolidate가 이 곳에 위치하는 이상 당연한 것이었다.
malloc_consolidate의 내부는 _int_malloc의 분석이 끝난 다음에 살펴보기로 하자.
이제 fastbin과 smallbin에서 청크를 찾지 못했다면 어떤흐름이 이어지는지 계속 살펴보자.
4. unsorted bin 탐색
/*
Process recently freed or remaindered chunks, taking one only if
it is exact fit, or, if this a small request, the chunk is remainder from
the most recent non-exact fit. Place other traversed chunks in
bins. Note that this step is the only place in any routine where
chunks are placed in bins.
The outer loop here is needed because we might not realize until
near the end of malloc that we should have consolidated, so must
do so and retry. This happens at most once, and only when we would
otherwise need to expand memory to service a "small" request.
*/
#if USE_TCACHE
INTERNAL_SIZE_T tcache_nb = 0;
size_t tc_idx = csize2tidx (nb);
if (tcache && tc_idx < mp_.tcache_bins)
tcache_nb = nb;
int return_cached = 0;
tcache_unsorted_count = 0;
#endif
for (;; )
{
int iters = 0;우선 tcache를 사용하는 경우 tc_idx, tcache_nb의 값을 설정해준 다음 return_cached와 tcache_unsorted_count를 0으로 설정해주는데 아직은 무슨 용도인지 모르겠다. 추후에 필요한 값인 듯 하다.
그리고 나서 for문이 존재하는데 이 for문은 여기서부터 _int_malloc이 종료될 때까지를 모두 감싸고 있는 거대한 반복문이다. 주석을 읽어보면 만일에 대비하여 retry를 하기 위해 존재하는 반복문인 듯 한데 대부분 한번만 실행된다고 하니 일단은 없는 셈 치고 봐도 될 듯 하다.
그리고 밑에 나올 또 다른 거대한 반복문인 while문 (for문 내부에 존재)을 위한 반복인자으로 보이는 iters를 선언하고 0으로 초기화한다.
주석을 참고하면 지금부터는 최근에 해제되거나 남은 청크들을 처리하여 알맞은 청크가 있다면 가져오고 탐색과정에서 지나치는 청크들을 알맞은 bin에 넣어준다고한다. 아마 이것이 unsorted bin 탐색 시에 탐색된 청크들은 크기에 따라 알맞은 bin으로 분류된다고 했던 부분인 듯 하다.
while문 내부를 살펴보자.
while ((victim = unsorted_chunks (av)->bk) != unsorted_chunks (av))
{
bck = victim->bk;
size = chunksize (victim);
mchunkptr next = chunk_at_offset (victim, size);
if (__glibc_unlikely (size <= CHUNK_HDR_SZ)
|| __glibc_unlikely (size > av->system_mem))
malloc_printerr ("malloc(): invalid size (unsorted)");
if (__glibc_unlikely (chunksize_nomask (nex t) < CHUNK_HDR_SZ)
|| __glibc_unlikely (chunksize_nomask (next) > av->system_mem))
malloc_printerr ("malloc(): invalid next size (unsorted)");
if (__glibc_unlikely ((prev_size (next) & ~(SIZE_BITS)) != size))
malloc_printerr ("malloc(): mismatching next->prev_size (unsorted)");
if (__glibc_unlikely (bck->fd != victim)
|| __glibc_unlikely (victim->fd != unsorted_chunks (av)))
malloc_printerr ("malloc(): unsorted double linked list corrupted");
if (__glibc_unlikely (prev_inuse (next)))
malloc_printerr ("malloc(): invalid next->prev_inuse (unsorted)");
우선 while문의 조건을 살펴보면 unsorted_chunks 매크로를 통해 가져온 청크의 bk에 해당하는 청크를 victim에 넣고 그것이 unsorted_chunks 매크로를 통해 가져온 청크와 같은지를 보고 있다. 같지 않다면 while문은 계속 반복된다.
우선 unsorted_chunks 매크로를 살펴보면 이는 곧 av→bins[0]과 동일하다. malloc_state구조체에서 bins 배열은 fastbin을 제외한 bin들을 관리하고 이 중 가장 첫 번째 요소가 unsorted bin이라고 했기 때문에 매크로 이름에서 알 수 있듯 unsorted bin 리스트를 가져온 것을 알 수 있다.
while문의 조건이 의미하는 것은 아까 small bin에서 했던 것과 비슷하게 unsorted bin이 비어있는지를 확인하는 것인 듯 하다. 따라서 이 반복문은 unsorted bin에 청크가 존재하는 한 반복될 것이다.
이제 while문 내부를 살펴보자.
우선 bck에 victim의 bk를 대입하고 size에는 victim의 size를, next에는 메모리상에서 victim 바로 다음에 존재한 청크를 대입한다.
그리고 다음과 같은 검증을 거친다.
- size가 헤더 사이즈보다 작거나 system_mem보다 크진 않은지를 확인
- next청크의 크기가 헤더 사이즈보다 작거나 system_mem보다 크진 않은지를 확인
- next chunk의 prev_size값이 size(=victim의 size)와 동일한지 확인
- bck(victim의 bk)의 fd가 victim인지, victim의 fd가 unsorted_chunks (av)인지 확인
- next의 prev_inuse flag가 set되어있는지 확인
확실히 검증 절차가 많다. 뭔가 특정 값을 이 절차들을 우회해서 변조하기는 거의 불가능에 가까워 보인다. (헤더, fd와 bk까지 검사하니까)
만약 검증절차를 모두 통과하면 계속 진행된다.
이제 본격적으로 알맞은 청크를 탐색할것으로 예상된다.
1) last remainder 청크 확인
/*
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;
}주석을 읽어보면, 할당 요청이 small request일 때에는 last remainder chunk가 unsorted bin에 존재하는 유일한 청크일 때에 한해 그것을 먼저 확인하라고 되어있다. 이 방식을 통해 small requests가 연속적으로 들어올 때 locality를 유지할 수 있다고 한다. 아마 비슷한 위치에 청크들을 할당시킬 수 있다는 의미일 것이다.
실제로 조건을 살펴보면 다음과 같다.
- nb가 small bin의 범위에 있고
bck == unsorted_chunks (av)일 때(bck는 victim의 bk이므로 victim의 bk가 unsorted_chunks(av)라면 victim이 unsorted bin의 유일한 청크인 상황이 될 것이다)victim == av->last_remainder일 때, 즉 victim이 last remainder 청크일 때(unsigned long) (size) > (unsigned long) (nb + MINSIZE)일 때, 즉 victim의 크기가 요청된 사이즈보다 충분히 클 때
종합해보면 small request이면서 last remainder chunk가 unsorted bin 존재하는 유일한 청크이며 그것의 크기가 요청을 처리하기에 충분하다면 조건문의 내부로 들어가는 것이며 이는 곧 주석이 의미하는 것과 동일하다.
따라서 이 조건문 내부에서는 last remainder chunk를 확인하는 과정이 있을 것이다.
내부를 살펴보자.
주석을 보면 split, reattach를 하라고 되어있다.
아마 요청 크기에 맞게 청크를 쪼개고 bin의 연결 관계를 정리한 다음 청크를 할당할 것이다.
우선 remainder_size 에 size-nb를 대입하는데 이는 필요한 만큼을 쪼개고 남은 크기이다.
그리고 remainder 에는 victim의 주소+nb만큼의 주소를 대입해주는데 이 역시 필요한 만큼을 쪼개고 남은 청크의 시작 주소이다.
다음으로는 unsorted_chunks (av) 의 fd와 bk를 remainder로 바꾸어준다. (처음엔 이게 도대체 뭐하는거지..? 라고생각했는데 생각해보니까 이 if문 내부로 들어오려면 unsorted bin에는 청크가 하나만 있던 상황이므로 unsorted bin의 유일한 청크를 remainder로만 업데이트 해준다고 생각하니 이해가 되었다.
그리고 av, 즉 arena에 해당하는 malloc_state구조체의 last_remainder값을 remainder로 바꾸어준다.
그 다음으로는 remainder의 bk와 fd를 unsorted_chunks (av) 로 바꾸어준다. (unsorted bin에 존재하는 유일한 청크로써 remainder를 넣어준다고 생각하면 편하다)
그리고 남은 청크의 사이즈(remainder_size)가 small bin의 범위가 아니라면 fd_nextsize와 bk_nextsize를 null로 설정해준다. 이 두 값은 large bin 사이즈의 청크에만 필요한 값으로 알고있느데 small bin범위가 아니라면 large bin의 범위에 속할 테니 필요할 두 값을 null로 초기화하는 과정인 듯 하다.
여기까지 청크를 쪼개고 bin의 연결관계 정리가 끝났다. 이제 쪼개놨던 청크(victim)을 할당할 차례이다.
각각 victim과 remainder의 헤더를 알맞게 세팅해주고 remainder의 메모리 상 인접 청크에 prev_size값도 알맞게 세팅해준다.
그리고 victim을 검증한 다음 void형 포인터 변수 p에 victim을 메모리 주소로 변환하여 대입하고 이를 return한다.
이 상황에 맞는 청크를 찾았다면 여기서 malloc이 종료될 것이다.
하지만 알맞은 청크가 없었다면 malloc은 계속 진행된다.
2) fit 청크 확인
/* remove from unsorted list */
if (__glibc_unlikely (bck->fd != victim))
malloc_printerr ("malloc(): corrupted unsorted chunks 3");
unsorted_chunks (av)->bk = bck;
bck->fd = unsorted_chunks (av);
/* Take now instead of binning if exact fit */
if (size == nb)
{
set_inuse_bit_at_offset (victim, size);
if (av != &main_arena)
set_non_main_arena (victim);
#if USE_TCACHE
/* Fill cache first, return to user only if cache fills.
We may return one of these chunks later. */
if (tcache_nb
&& tcache->counts[tc_idx] < mp_.tcache_count)
{
tcache_put (victim, tc_idx);
return_cached = 1;
continue;
}
else
{
#endif
check_malloced_chunk (av, victim, nb);
void *p = chunk2mem (victim);
alloc_perturb (p, bytes);
return p;
#if USE_TCACHE
}
#endif
}
코드를 보니 실제로 victim의 bk인 bck의 fd가 victim인지 확인하는 검증절차를 거친 다음, 냅다 unsorted bin에서 청크를 제거해버리길래 뭐하는거지? 싶어서 밑을 먼저 간단하게 살펴보고 왔더니 진행이 이런 식으로 이루어지는 듯 하다.
⇒ 우선 victim청크가 할당 요청이 들어온 크기와 동일하다면 victim청크를 할당한다
⇒ 만약 아니라면 bin으로 분류한다.
⇒ last remainder청크 확인 절차까지 포함한 이 루틴을 unsorted bin에 청크가 없어질 때까지 혹은 청크의 할당이 이루어질 때까지 반복한다. (while문에 의한 반복)
좀 더 정리해보자면 이 거대한 while문의 동작은 다음과 같다.
unsorted bin의 청크를 순차적으로 가져와 last remainder ⇒ fit chunk 순으로 확인하고 조건에 맞다면 할당, 아니라면 bin으로 분류하는 과정을 unsorted bin에 청크가 존재하는 한 반복하여 시행한다.
따라서 이 부분은 청크가 fit chunk인지 확인하는 부분일 것이다.
실제로 if문의 조건을 보면, size와 nb가 동일한지를 확인하고 있다. 만약 동일하다면 현재 보고 있는 청크가 fit chunk라는것이며 조건문 내부로 들어간다.
조건문 내부를 보면 victim 청크의 할당 절차가 존재한다. (일단 tcache부분은 무시하자.)
메모리 상의 다음 청크에 prev_inuse flag를 set하고 청크를 검증한 다음 void 형 포인터 p에 victim을 메모리 주소로 변환해 대입하고 이를 return하고 있다. 만약 여기서 return이 이루어진다면 malloc은 여기서 종료된다. 만약 그렇지 않다면 이 청크를 알맞은 bin에 넣는 과정으로 이어질 것이다.
잠깐 미뤄뒀던 tcache부분을 살펴보자면, 만약 nb가 tcache의 범위 내에 있었다면 이전에 tcachenb가 설정되어있었을 것이므로 tcache_nb 부분은 참이 될 것이고 `tcache->counts[tc_idx] < mp.tcache_count` 라는 조건은 해당하는 인덱스의 tcache에 공간이 있다면 참이 될 것이다.
따라서 현재 요청된 크기가 tcache 범위 내에 있으며 그 인덱스의 tcache 리스트에 공간이 있다면 청크의 할당이 이루어지기 전에 먼저 이 청크를 tcache에 넣어버린다. 그리고 초기값을 0으로 설정했던 return_cached 라는 값을 1로 바꾸어준다. return_cached 는 이 while문 내에서 tcache로 들어간 청크가 존재한다면 1로 바뀌는 값인가보다. 그리고 continue가 있기 때문에 아래의 모든 절차를 건너뛰고 다음 unsorted bin의 청크를 탐색하는 절차로 넘어갈 것이다.
조금 특이하게 느껴졌던게, 요청에 fit하는 청크를 발견했음에도 조건만 맞는다면 이를 할당하는 것이 아닌 tcache로 먼저 옮기는 것이 신기했다. 뭔가 직관적으로 보기엔 바로 할당해버리는게 더 효율적일 것 같은데 종합적으로 판단했을 때는 tcache에 넣어버리는 것이 더 효율적인가보다. 아무래도 동적할당은 비슷한 크기가 계속해서 이루어지는 경우가 많으니까 다음 번의 동적할당을 고려한다면 지금은 이미 bin의 탐색 절차까지 와버렸으니 계속 탐색을 이어간 다음 다음 동적 할당에서 탐색 시간을 줄이는 게 더욱 이득이라서 그런 것일까? 이유가 좀 궁금해졌다.
물론 조건이 맞지 않는다면 원래대로 fit chunk를 할당하고 malloc을 끝내버릴 것이다.
코드를 계속보자.
3) 청크를 bin에 분류
/* place chunk in bin */
if (in_smallbin_range (size))
{
victim_index = smallbin_index (size);
bck = bin_at (av, victim_index);
fwd = bck->fd;
}주석에서도 알 수 있다시피 이제 청크를 알맞은 bin에 분류한다.
먼저 size(victim의 크기)가 smallbin 범위에 들어간다면 조건문 내부로 들어간다.
victim_index를 설정해주고 인덱스값을 바탕으로 이에 해당하는 smallbin리스트를 가져오고 bck에 bin_at (av, victim_index) , fwd에 bin_at (av, victim_index) 의 fd를 대입한다. 아마 삽입할 bin의 bk에 bck를 fd에 fwd를 대입해주어 bin_at (av, victim_index) 과 bin_at (av, victim_index) 의 fd 사이에 victim을 삽입해주는 듯 하다.
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 (chunk_main_arena (bck->bk));
if ((unsigned long) (size)
< (unsigned long) chunksize_nomask (bck->bk))
{
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 (chunk_main_arena (fwd));
while ((unsigned long) size < chunksize_nomask (fwd))
{
fwd = fwd->fd_nextsize;
assert (chunk_main_arena (fwd));
}
if ((unsigned long) size
== (unsigned long) chunksize_nomask (fwd))
/* Always insert in the second position. */
fwd = fwd->fd;
else
{
victim->fd_nextsize = fwd;
victim->bk_nextsize = fwd->bk_nextsize;
if (__glibc_unlikely (fwd->bk_nextsize->fd_nextsize != fwd))
malloc_printerr ("malloc(): largebin double linked list corrupted (nextsize)");
fwd->bk_nextsize = victim;
victim->bk_nextsize->fd_nextsize = victim;
}
bck = fwd->bk;
if (bck->fd != fwd)
malloc_printerr ("malloc(): largebin double linked list corrupted (bk)");
}
}
else
victim->fd_nextsize = victim->bk_nextsize = victim;
}만약 largebin크기의 청크였다면 이 else문이 실행될 것이다. 우선 victim_index, bck, fwd값을 이전과 동일한 원리로 세팅해준다.
하지만 large bin 크기의 청크는 그 외에도 뭔가가 많다. 계속 살펴보자.
주석을 보니 large bin의 경우에는 정렬 순서를 유지해 줘야 하기 때문에 처리할 것이 더 많은 듯 하다.
실제로 large bin은 여러 크기의 청크를 한 연결리스트에서 관리하며 재할당 시의 효율을 위해 내부의 청크들이 내림차순으로 정렬되어 있다고 배웠다. 따라서 단순히 bin_at 매크로로 가져온 청크와 그 청의 fd 사이에 이 청크를 삽입하는 것이 아니라 크기에 따라 알맞은 자리를 찾아주는 과정이 필요하다.
우선 fwd와 bck의 일치여부를 확인하는데, 만약 이 두개가 일치한다면 largebin에 청크가 없는 상태라는 의미이다. 이는 곧 정렬에 관계없이 victim을 삽입만 해주면 된다는 의미이며 바로 맨 밑의 else문으로 빠져 victim->fd_nextsize = victim->bk_nextsize = victim; 코드가 실행될 것이다. 즉, 별다른 조치 없이 largebin에 넣기 위한 fd_nextsize , bk_nextsize 만 설정된 상태로 실제로 victim청크를 link하기 위한 코드로 이어진다.
하지만 조건문이 참이라면 이는 곧 largebin에 청크가 있다는 의미이므로 if문 내부로 들어가 알맞은 자리를 찾아주기 위한 과정이 시작된다.
만약 bck→bk(해당 largebin에 존재하는 가장 작은 청크)보다 size가 작다면 주석에 나온대로 smallest보다 작다는 의미이므로 바로 알맞은 위치를 찾을 수가 있다. 즉, bck와 bck의 bk 사이에 victim을 삽입해주면 된다. 따라서 이에 맞게 bck와 fwd를 각각 bck와 bck의 bk로 바꾸어준다음 victim과 인접 청크들의 fd_nextsize와 bk_nextsize값을 설정해준다.
하지만 bck→bk보다 size가 작지 않다면 본격적으로 알맞은 자리를 찾아주어야 한다.
좀 더 보기 편하게 이 부분만 따로 코드를 살펴보자.
else
{
assert (chunk_main_arena (fwd));
while ((unsigned long) size < chunksize_nomask (fwd))
{
fwd = fwd->fd_nextsize;
assert (chunk_main_arena (fwd));
}
if ((unsigned long) size
== (unsigned long) chunksize_nomask (fwd))
/* Always insert in the second position. */
fwd = fwd->fd;
else
{
victim->fd_nextsize = fwd;
victim->bk_nextsize = fwd->bk_nextsize;
if (__glibc_unlikely (fwd->bk_nextsize->fd_nextsize != fwd))
malloc_printerr ("malloc(): largebin double linked list corrupted (nextsize)");
fwd->bk_nextsize = victim;
victim->bk_nextsize->fd_nextsize = victim;
}
bck = fwd->bk;
if (bck->fd != fwd)
malloc_printerr ("malloc(): largebin double linked list corrupted (bk)");
}우선 while문을 통해서 size보다 작거나 같은 size값의 청크를 찾을 때까지 fwd를 fwd의 fd로 업데이트해준다. 만약 알맞은 위치가 찾아진다면 적절한 위치가 fwd에 저장된 상태로 while문을 빠져나온다.
이후에도 두 가지 경우로 나뉠 수가 있는데 바로 size가 fwd의 size와 같은 경우와 더 큰 경우이다.
⇒만약 같다면, 주석에 나온대로 항상 second position에 삽입해준다. 따라서 fwd는 fwd의 fd가 될 것이다.
⇒ 만약 같지 않다면 fwd는 이미 올바른 위치를 찾은 상태이므로 fwd는 건들 필요가 업고 victim과 fwd의 bk_nextsize, fd_nextsize를 올바르게 설정해준다. 그 과정에서 fwd의 bk_nextsize의 fd_nextsize가 fwd와 동일한지 검증하는 절차가 존재한다.
이렇게 각각 경우에 따라 올바른 fwd가 설정되고 나면 당연히 bck는 fwd의 bk가 될 것이다.
그리고 bck의 fd가 fwd와 동일한지 검증해준다. (검증 절차가 매우 많다)
mark_bin (av, victim_index);
victim->bk = bck;
victim->fd = fwd;
fwd->bk = victim;
bck->fd = victim;
#if USE_TCACHE
/* If we've processed as many chunks as we're allowed while
filling the cache, return one of the cached ones. */
++tcache_unsorted_count;
if (return_cached
&& mp_.tcache_unsorted_limit > 0
&& tcache_unsorted_count > mp_.tcache_unsorted_limit)
{
return tcache_get (tc_idx);
}
#endif
#define MAX_ITERS 10000
if (++iters >= MAX_ITERS)
break;
}
#if USE_TCACHE
/* If all the small chunks we found ended up cached, return one now. */
if (return_cached)
{
return tcache_get (tc_idx);
}
#endif
여기까지 진행이 된다면 small bin이던 large bin이던 간에 victim을 삽입할 알맞은 bck와 fwd가 설정된 상태일 것이다. 따라서 victim의 bk에 bck, victim의 fd에 fwd를 넣고 fwd의 bk와 bck의 fd에는 victim을 넣어 fwd, victim, bck를 연결, 즉 victim을 bin의 알맞은 자리에 삽입해준다.
mark_bin 은 뭔가 해서 봤는데 비트맵과 관련된 것인듯 하다. 비트맵이 뭔지 몰라서 찾아보니 bin들의 정보를 비트를 사용해서 기록하는 값으로 빈 검색을 간소화하는 데 도움을 준다고 한다. malloc_state구조체 내에 binmap이라는 이름으로 존재하며 bin들을 4개의 영역으로 나누어서 정보를 배치한다고 한다. mark_bin 매크로를 사용해서 binmap에 bin에 청크를 삽입한 정보를 표시해주는 것 같다.
만약 tcache가 사용된다면 tcache_unsorted_count를 1 증가 시켜준다. 이는 초기값 0으로 설정되어 선언되었던 값인데 tcache의 삽입 없이 여기까지 진행되는 횟수를 카운트하는 변수인가보다.
그리고 returncached가 1이면서(이전에 fit chunk를 찾았으면서 tcache에 자리가 있다면 tcache에 삽입하고 1로 바꾸어줬던 값이다. 따라서 이 조건문의 진입 조건 중에 이 전에 while문 내부에서의 tcache삽입이 있었는지가 있다는 의미이다) unsorted list에서 제거될 수 있는 최대의 청크 수를 의미하는 tcache_unsorted_limit 가 0보다 크거나 tcache_unsorted_count보다 작으면 tcache의 청크를 반환한다. 그런데 mp의 tcache_unsorted_limit 값은 0으로 선언되어 있는데 그렇다면 0보다 클수가 없는 것 아닌가…? 이 부분은 잘 모르겠다… 확실하진 않지만 대충 tcache에서 할당할 수 있는 청크가 존재하면 여기서 할당이 한 번 더 이루어질 수 있는 듯 하다. 왜냐하면 반복문 내부에 fit 청크를 tcache에 삽입하는 루틴이 있기 때문에 __libc_malloc에서 tcache청크의 재할당이 이루어지지 않았더라도 이후 tcache에 재할당 가능한 청크가 생길 수 있기 때문이다. 이전에 왜 tcache에 갑자기 청크를 넣는 건지 의아했었는데 어차피 tcache할당의 기회가 한 번 더 있기 때문에 그런 것도 있었나보다. 그런데도 여전히 왜 그러는지는 의문이긴 하지만…
그리고 이제 while문 반복 루틴의 마지막이 보이는데 이전에 살펴봤던 바로는 while문의 반복 조건은 unsorted bin에 청크가 존재하는지의 여부였다. 그런데 while문의 반복인자인 iters가 10000 보다 크거나 같다면 while문을 빠져나간다고 되어있으므로 결론적으로 while문의 탈출 조건은 다음과 같아진다.
- unsorted bin에 청크가 하나도 남아있지 않음
- 반복횟수가 10000을 넘었을 때
- 특정 부분에서 동적할당이 이루어졌을 때(아예 malloc자체가 종료)
이 조건들이 충족되기 전까지는 while문이 계속해서 반복되면서 알맞은 청크를 찾거나, unsorted bin의 청크를 bin에 분류할 것이다.
그리고 return_cached가 set되어있다면 tcache의 청크를 재할당하는 과정이 한 번 더 존재하는데.. 이건 while문 반복의 마지막 차례에 tcache로의 삽입이 이루어져 continue 때문에 tcache 재할당까지 도달을 못하는 경우 때문에 while문 밖에도 한 번 더 존재하는 것일 듯 하다.
5. large bin탐색
만약 이 부분까지 실행흐름이 진행된다면 이는 곧 unsorted bin에서의 할당이 실패한 경우일 것이다. 아마 이제 large bin의 탐색이 이루어지지 않을까 예상해볼 수 있다.
/*
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) chunksize_nomask (victim)
>= (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)
&& chunksize_nomask (victim)
== chunksize_nomask (victim->fd))
victim = victim->fd;
remainder_size = size - nb;
unlink_chunk (av, victim);
주석을 살펴보니 large bin의 탐색 차례가 맞는 듯 하다.
일단 가장 큰 if문의 조건을 살펴보면 nb가 smallbin의 범위에 있지 않다면, 즉 largebin의 범위에 있다면 if문 내부로 들어가게 된다.
우선 bin_at 을 통해 idx에 해당하는 bin리스트를 bin에 가져온다.
그리고 또 하나의 두 번째로 큰 조건문이 존재하는데 이는 가져온 bin이 비어있지는 않은지, 그 bin의 largest chunk가 요청크기보다 크거나 같은지를 검사한다. 만약 bin이 비어있지 않고 bin의 가장 큰 청크가 요청크기보다 크거나 같다면 if문 내부로 들어가고 그렇지 않다면 bin이 비어있거나 bin에 존재하는 가장 큰 청크가 요청보다 작다는 것이기 때문에 if문 내부로 들어가지 않고 다음 흐름을 이어간다. (미리 흐름을 살펴보고 왔더니 인덱스값을 증가 시켜 large bin탐색을 이어가는 듯 하다.)
만약 if문 내부로 들어간다면 이는 적어도 지금 보고 있는 bin에는 사용가능한 청크가 있다는 것이기 때문에 할당이 무조건 이루어질 것이다.
if문 내부로 들어가면 해당 bin의 가장 작은 청크부터 시작해 요청크기보다 청크의 크기가 크거나 같아지는 순간까지 while문을 통해 청크를 탐색한다. 만약 while문을 빠져나갔다는 것은 victim이 처음으로 요청크기와 크거나 같아진 순간이라는 것이므로 while문 직후이 victim이 재할당 대상이 될 것이다.
그리고 victim청크를 분할하기에 앞서 만약 victim이 bin의 last chunk(최소청크)가 아니면서 victim의 크기가 victim의 fd의 크기와 같다면 victim을 victim의 fd로 바꾸어준다. 그냥 동일 크기의 청크가 존재한다면 무조건 forward에있는 것을 할당하는 것이 원칙인가보다.
어쨋든 알맞게 victim을 정하고 나면 청크를 분할하기 위한 절차가 시작된다. 우선 victim의 size에 해당하는 size에서 요청 크기인 nb를 빼서 remainder_size에 저장해준다. 그리고 unlink_chunk 로 victim청크를 av(아레나)로부터 unlink해준다.
/* Exhaust */
if (remainder_size < MINSIZE)
{
set_inuse_bit_at_offset (victim, size);
if (av != &main_arena)
set_non_main_arena (victim);
}
/* 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))
malloc_printerr ("malloc(): corrupted unsorted chunks");
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;
}
}그런데 만약 remainder_size가 MINSIZE 보다 작다면, 분할하고 남은 청크가 MINSIZE 보다 작아지면 안되기 때문에 바로 victim의 메모리상 인접 청크에 prev_inuse flag를 설정하고 해당 청크를 할당해버린다.
하지만 그런 경우가 아니라면 else문으로 들어가 분할 절차를 계속한다.
우선 remainder이라는 변수에 victim의 주소+nb의 주소를 넣어준다. 이는 victim을 필요한 만큼 쪼개고 남은청크의 시작 주소이다.
그리고 remainder 청크를 unsorted bin에 넣어준다.
좀 더 자세하게 보면, 다음과 같다. bck에 unsorted_chunks (av) 를 , fwd에 bck의 fd를 대입하여 remainder, 즉 쪼개고 남은 청크를 fwd와 bck의 사이에 삽입해준다. 그 과정에서 fwd의 bk와 bck가 같은지를 확인하는 검증 절차가 존재한다. 그리고 만약 remainder_size가 large bin의 범위에 들어간다면 fd_nextsize와 bk_nextsize를 null로 초기화해준다.
그리고 victim과 remainder를 각각 새로운 크기에 맞게 헤더값을 세팅해주고 remainder의 경우에는 메모리 상의 인접 청크에 prev_size도 알맞게 바꾸어준다.
그리고 victim청크를 할당해준다.
만약 여기서 할당이 이루어지지 못하면 계속 코드를 진행한다.
여기서부터는 이전 largebin에서 알맞은 청크를 찾지 못했을 때 도달하게 되는 코드이다.
첫 부분을 보면 idx를 1 증가시켜 bin을 계속 탐색한다는 것을 알 수 있다.
/*
Search for a chunk by scanning bins, starting with next largest
bin. This search is strictly by best-fit; i.e., the smallest
(with ties going to approximately the least recently used) chunk
that fits is selected.
The bitmap avoids needing to check that most blocks are nonempty.
The particular case of skipping all bins during warm-up phases
when no chunks have been returned yet is faster than it might look.
*/
++idx;
bin = bin_at (av, idx);
block = idx2block (idx);
map = av->binmap[block];
bit = idx2bit (idx);
주석을 살펴보면 탐색을 하되 청크 선택의 원칙은 적합한 청크 중 가장 작은 청크라고 한다.
그리고 이전에 잠깐 봤던 개념인 bitmap을 활용한 탐색이 이루어지는 것 같다.
우선 idx를 1 증가 시키고, 그 인덱스에 해당하는 bin리스트를 bin에 가져온다.
그리고 그 bin에 해당하는 binmap을 가져오기 위한 block값을 가져오고 (이전에 살펴보았을 때, 모든 bin을 4개의 binmap에 나누어 관리한다고 했으므로 인덱스값을 바탕으로 해당하는 block값을 idx2block 으로 가져오는 듯 하다) map이라는 변수에 해당하는 binmap을 대입한다. 또한 idx를 비트값으로 변환하여 bit에 저장한다.
일단 이 부분을 자세하게 이해하려면 binmap의 개념을 확실하게 짚고 넘어가야 한다.
우선 binmap은 총 4개가 존재하며, 각 binmap당 담당하는 bin은 다음과 같다.
binmap[0] : 0 ~ 31, binmap[1] : 32 ~ 64, binmap[2] : 65 ~ 96, binmap[3] : 97 ~128그리고 만약 특정 bin에 free청크가 배치된다면 그 bin에 해당하는 binmap에 그 bin에 대한 bit가 배치된다고 한다.
해당 bin에 대한 bit를 계산하는 매크로가 바로 idx2bit 인 듯 하다.
그러니까 idx2bit 매크로를 살펴보자.
#define **idx2bit**(i) ((1U << ((i) & ((1U << **BINMAPSHIFT**) - 1))))
다음과 같은 형태로 되어있다. (BINMAPSHIFT 는 5이다. )
즉, idx2bit(idx) == 1U << ( idx & ((1U << BINMAPSHIFT) - 1)) == 1 << (idx & 31) 이다.
binmap을 사용하면 bin검색을 간소화할 수 있다고 했는데, 정확하진 않지만 binmap의 비트를 확인하여 해당 크기의 free chunk가 존재하는지를 바로 확인할 수 있기 때문인 것 같다.
일단 여기까지 보고 코드를 계속 봐보자.
for (;; )
{
/* Skip rest of block if there are no more set bits in this block. */
if (bit > map || bit == 0)
{
do
{
if (++block >= BINMAPSIZE) /* out of bins */
goto use_top;
}
while ((map = av->binmap[block]) == 0);
bin = bin_at (av, (block << BINMAPSHIFT));
bit = 1;
}
/* Advance to bin with set bit. There must be one. */
while ((bit & map) == 0)
{
bin = next_bin (bin);
bit <<= 1;
assert (bit != 0);
}
/* Inspect the bin. It is likely to be non-empty */
victim = last (bin);
또다시 for문이 등장하는데 뭔가 알맞은 bin을 찾을 때까지 계속 반복이 이루어지고, 이 for문을 빠져나가기 위한 방법은 return으로 인해 malloc이 종료되거나, goto로 인해 use_top으로 빠지거나 둘 중 하나인 듯 하다.
우선 가장 처음으로 bit(=idx2bit (idx))가 map(=av->binmap[block])보다 크거나 bit==0인지를 확인하고 있는데, 이 조건이 참이 된다는 것은 우리가 원하는 idx의 bin에 free된 청크가 존재하지 않는다는 뜻이다. 따라서 if문 내부에 들어가면 binmap[]의 값이 0이 아닌 binmap을 찾을 때까지 binmap의 인덱스 값인 block을 증가시켜 탐색하고 만약 모든 binmap이 다 0이라면 use_top이라는 부분으로 goto를 통해 이동한다. 이 부분은 large bin탐색 부분을 다 본 다음 살펴볼 예정이다.
확실히 이 부분만 봐도 수많은 largebin 리스트들을 일일히 확인하지 않아도 최대 4개의 binmap block만 살펴보면 되니까 만약 필요한 청크가 largebin에 없었다고 가정한다면 훨씬 효율적인 방법이라는 것을 알 수 있다.
어쨌든 goto를 통해 빠지지 않고 do-while문을 빠져나왔다는 것은 0이 아닌 binmap block이 있었다는 의미일 것이고, 0이 아닌 다음 binmap block을 찾았다면 다음 코드가 이어서 계속 실행될 것이다.
우선 bin_at 매크로를 통해서 해당 block의 범위 안에 드는 가장 첫 번째 bin을 가져온다. 그리고 그것의 bit를 1로 설정해준다.
처음에는 왜 bit를 1로 설정하는 것인지 이해가 가지 않았는데 직접 예시를 들어서 계산해보니 이해가 갔다. 만약에 지금 보고있는 binmap이 binmap[3]이라고 가정하면, 이 block에 해당하는 가장 첫 번째 bin에 해당하는 인덱스는 3 << BINMAPSHIFT = 96 이 될 것이다. (음.. 실제로 binmap[3]의 첫 인덱스 값은 97이긴 하다. 근데 이는 실질적인 코드 상에서 최적화를 하면서 사용하지 않는 첫 번째와 마지막 인덱스를 아예 제외시켜버린 것과 연관이 있을 듯 하다). 어쨋든 96이라고 가정하면 이 96의 비트값을 계산해보면 1 << (96 & 31) = 1 << 0 = 1 이다. 아마 어떤 block값에 이를 계산해도 가장 첫 번째 인덱스의 비트값은 1일 것이다. 그래서 초기 비트 값을 1로 설정하는 것이다.
어쨋든 보고 있는 block의 첫 번째 bin에 해당하는 정보들을 설정해주었으면 이제 bit & map의 값이 0이 아닐 때까지 다음 bin을 계속 탐색한다. bit&map가 0이라는 것은 해당 bit에 해당하는 인덱스의 bin에는 free된 청크가 없다는 것이므로 while문을 벗어날 때까지, 즉 free청크가 존재하는 bin을 찾을 때까지 bin의 정보를 업데이트하면서 탐색한다.
만약 while문을 벗어났다면, free 청크가 존재하는 bin을 찾았다는 것이다. 이제 그 bin을 대상으로 한 탐색을 시작한다. victim에 그 bin의 last chunk를 대입해준다.
/* If a false alarm (empty bin), clear the bit. */
if (victim == bin)
{
av->binmap[block] = map &= ~bit; /* Write through */
bin = next_bin (bin);
bit <<= 1;
}
else
{
size = chunksize (victim);
/* We know the first chunk in this bin is big enough to use. */
assert ((unsigned long) (size) >= (unsigned long) (nb));
remainder_size = size - nb;
/* unlink */
unlink_chunk (av, victim);
/* Exhaust */
if (remainder_size < MINSIZE)
{
set_inuse_bit_at_offset (victim, size);
if (av != &main_arena)
set_non_main_arena (victim);
}
/* 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))
malloc_printerr ("malloc(): corrupted unsorted chunks 2");
remainder->bk = bck;
remainder->fd = fwd;
bck->fd = remainder;
fwd->bk = remainder;
/* advertise as last remainder */
if (in_smallbin_range (nb))
av->last_remainder = 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;
}
}어떻게 그런 상황이 생기는 지는 모르겠지만 bit값이 잘못될 때도 있나보다. 그래서 우리가 지금 보고 있는 bin이 만약 비어있다면 (victim == bin이라면) binmap에서 비트 정보를 바로잡아주고 또 다음 bin을 탐색한다. 그 이후의 탐색은 어떻게 되는건가 봤더니 애초에 지금 이 코드가 for문 내부에 존재했기 때문에 bin에는 다음 bin의 정보를, 그리고 그에 해당하는 비트를 bit에 저장한 상태로 for문의 초기로 돌아가 탐색을 이어가는 것 같다.
그리고 bin이 비어있는 것이 아니라면 else문으로 가서 청크를 할당하기 위한 절차를 밟는다.
우선 size에 victim의 크기값을 담아준다. 여기서 size는 당연히 요청 할당크기 보다 커야 한다.
remainder_size에 size에서 nb를 뺀 값을 담아준다. 분할 루틴에서 여러번 봤듯이 이는 필요한 만큼의 청크를 쪼개고 남은 청크의 크기이다.
이전에 청크를 쪼갰던 절차와 동일한 절차가 이루어진다.
victim을 arena로 부터 unlink하고, 만약 remainder_size가 MINSIZE보다 작으면 그냥 victim을 그대로 할당해주고, 아니라면 청크를 쪼개서 remainder청크는 unsortedbin에 삽입하고 쪼갠 청크를 할당한다.
6. top chunk분할 /sysmalloc
이제 아까 나중에 보기로 했던 use_top부분을 보자.
이 부분은 large bin에서도 알맞은 청크를 발견하지 못한다면 도달하게 되는 부분이다.
use_top:
/*
If large enough, split off the chunk bordering the end of memory
(held in av->top). Note that this is in accord with the best-fit
search rule. In effect, av->top is treated as larger (and thus
less well fitting) than any other available chunk since it can
be extended to be as large as necessary (up to system
limitations).
We require that av->top always exists (i.e., has size >=
MINSIZE) after initialization, so if it would otherwise be
exhausted by current request, it is replenished. (The main
reason for ensuring it exists is that we may need MINSIZE space
to put in fenceposts in sysmalloc.)
*/
victim = av->top;
size = chunksize (victim);
if (__glibc_unlikely (size > av->system_mem))
malloc_printerr ("malloc(): corrupted top size");
if ((unsigned long) (size) >= (unsigned long) (nb + MINSIZE))
{
remainder_size = size - nb;
remainder = chunk_at_offset (victim, nb);
av->top = remainder;
set_head (victim, nb | PREV_INUSE |
(av != &main_arena ? NON_MAIN_ARENA : 0));
set_head (remainder, remainder_size | PREV_INUSE);
check_malloced_chunk (av, victim, nb);
void *p = chunk2mem (victim);
alloc_perturb (p, bytes);
return p;
}
이 부분에서는 top chunk를 사용한다. victim에 top청크의 베이스 주소를 넣어주고, size는 victim의 size가 된다. 그리고 size가 av->system_mem보다 큰지 확인하는 검증 절차를 거친다.
이후 size가 요청 사이즈보다 큰지 아닌지의 여부에 따라 나누어 처리한다.
만약 top청크의 size가 요청 사이즈보다 크다면 단순히 top청크를 쪼개서 쪼갠 청크를 할당해준다.
이 할당이 끝나고 나면 top청크의 크기는 줄어든 상태일 것이다.
이 부분은 메모리 할당 요청이 들어왔을 때, 사용할 적절한 Free Chunk가 없으면 Top Chunk를 쪼개어 사용한다고 배웠던 것과 일치한다.
하지만 요청 사이즈가 top chunk의 사이즈보다 크다면 어떻게 할까?
/* When we are using atomic ops to free fast chunks we can get
here for all block sizes. */
else if (atomic_load_relaxed (&av->have_fastchunks))
{
malloc_consolidate (av);
/* restore original bin index */
if (in_smallbin_range (nb))
idx = smallbin_index (nb);
else
idx = largebin_index (nb);
}
/*
Otherwise, relay to handle system-dependent cases
*/
else
{
void *p = sysmalloc (nb, av);
if (p != NULL)
alloc_perturb (p, bytes);
return p;
}
} //-->for문
}//-->함수 전체우선 fastchunk가 존재하는지 아닌지에 따라 경우가 나뉘어진다. 만약 fastbin에 청크가 존재한다면 malloc_consolidate를 통해서 fastbin의 청크들을 병합한다.
그리고 원래의 bin index를 복구해준다.
그리고 fastchunks가 존재하지 않으면 else문으로 간다. 이 부분을 보면 sysmalloc이라는 함수를 통해서 청크를 할당하고 반환한다. 내가 알기론 sysmalloc의 내부에서 필요에 따라 sbrk가 호출되는 것으로 알고 있는데, 이는 추후에 sbrk에 대한 분석 시에 sysmalloc을 제대로 분석해보면서 자세히 알아보아야 겠다.
결론
종합해보자면, _int_malloc은 fastbin⇒smallbin 탐색 ⇒malloc_consolidate⇒ unsorted bin탐색(last remainder확인⇒ unsorted bin내의 fit청크 확인⇒아니면 bin으로 분류를 반복) ⇒ largebin탐색⇒ (topchunk를 쪼개서 할당/sysmalloc을 통한 할당)의 순서로 진행된다.
역시나 tcache 청크의 재할당은 __libc_malloc에서 이루어지므로 _int_malloc내부엔 tcache의 청크를 재할당하는 것은 존재하지 않았다. (unsorted bin탐색 과정에서 tcache로 들어가게 된 청크 할당하는 것을 제외한다면)
각종 bin에 대해서 배울 때 잘 이해가 되지 않았던 것들을 보다 확실하게 알 수 있었던 것 같다.
