linking과정은 https://k0n9.tistory.com/entry/heap%EC%9D%98-%EA%B0%9C%EB%85%90-4 에 나오는 그림을 참고하면 좋다.
__libc_malloc
아래는 malloc함수 호출시 실행되는 코드이다.
//__libc_malloc 2.23
void *
__libc_malloc (size_t bytes)
{
mstate ar_ptr;
void *victim;
void *(*hook) (size_t, const void *)
= atomic_forced_read (__malloc_hook);
if (__builtin_expect (hook != NULL, 0))
return (*hook)(bytes, RETURN_ADDRESS (0));
arena_get (ar_ptr, bytes);
victim = _int_malloc (ar_ptr, bytes);
/* Retry with another arena only if we were able to find a usable arena
before. */
if (!victim && ar_ptr != NULL)
{
LIBC_PROBE (memory_malloc_retry, 1, bytes);
ar_ptr = arena_get_retry (ar_ptr, bytes);
victim = _int_malloc (ar_ptr, bytes);
}
if (ar_ptr != NULL)
(void) mutex_unlock (&ar_ptr->mutex);
assert (!victim || chunk_is_mmapped (mem2chunk (victim)) ||
ar_ptr == arena_for_chunk (mem2chunk (victim)));
return victim;
}
libc_hidden_def (__libc_malloc)
하나하나 살펴보자
atomic_forced_read로 __malloc_hook 를 읽어 hook포인터에 저장한다.
__malloc_hook 포인터(hook)가 지정되어 있을 시 hook 함수 실행된다.
즉, hook함수는 malloc함수가 동작할 때 실행되는 함수를 가리키는 포인터이다. 이 함수는 malloc함수가 메모리 할당을 수행하기 전에 실행되어 추가적인 처리를 수행하도록 도와준다.
ar_ptr에 arena구조체 주소를 저장하고 mutext_lock 을 설정한다.
_int_malloc 함수를 호출하여 chunk를 할당하고 할당된 chunk의 주소는 victim에 저장한다.
!victim이 참이면 victim이 0이라는 것이고, ar_ptr != NULL이 참이면 arena 포인터는 할당되었다는 것이다. 이 의미는 할당이 제대로 되지 않았다는 것이다. 그래서 다시 재할당을 시도한다.
할당이 완료되면 mutex_unlock을 해준다.
victim이 NULL이아니고 || victim이 가리키는 영역이 mmapped 된 경우가 아니고 || victim의 arena가 ar_ptr이 아니라면 assert 오류가 발생한다.
메모리 주소를 반환하는 실질적인 함수인 __int_malloc을 보자.
__int_malloc
//_int_malloc 2.23
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;
/*
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 traps (returning 0) request sizes
that are so large that they wrap around zero when padded and
aligned.
*/
checked_request2size (bytes, nb);
/* 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;
}
/*
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 = *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;
}
}
/*
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;
}
}
}
/*
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 (have_fastchunks (av))
malloc_consolidate (av);
}
/*
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.
*/
for (;; )
{
int iters = 0;
while ((victim = unsorted_chunks (av)->bk) != unsorted_chunks (av))
{
bck = victim->bk;
if (__builtin_expect (victim->size <= 2 * SIZE_SZ, 0)
|| __builtin_expect (victim->size > av->system_mem, 0))
malloc_printerr (check_action, "malloc(): memory corruption",
chunk2mem (victim), av);
size = chunksize (victim);
/*
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;
}
/* remove from unsorted list */
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)
victim->size |= NON_MAIN_ARENA;
check_malloced_chunk (av, victim, nb);
void *p = chunk2mem (victim);
alloc_perturb (p, bytes);
return p;
}
/* place chunk in bin */
if (in_smallbin_range (size))
{
victim_index = smallbin_index (size);
bck = bin_at (av, victim_index);
fwd = bck->fd;
}
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;
#define MAX_ITERS 10000
if (++iters >= MAX_ITERS)
break;
}
/*
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;
}
}
/*
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);
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);
/* 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 (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 2";
goto errout;
}
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;
}
}
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 ((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;
}
/* When we are using atomic ops to free fast chunks we can get
here for all block sizes. */
else if (have_fastchunks (av))
{
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;
}
}
}하나하나 분석해보자
nb = 요청한 size + header
idx = 할당에 뎐관된 bin의 index
bin = 할당에 연관된 ibn
victim = 할당 가능 여부를 검사중인 chunk
size = 특정 chunk의 크기
victim_index = 특정 chunk의 bin의 index
remainder = 분리되고 남은 remainder
remainder_size = remainder의 size
block, bit, map = bit map을 탐색하는데 필요한 것
fwd, bck = linking에 필요한 변수
errstr = 에러발생시 출력되는 문자열
요청한 크기를 정렬하고 header를 더해서 nb에 저장한다.
av == NULL이라면 사용가능한 arena가 없는 경우이고 그러면 nb만큼 sysmalloc으로 chunk를 할당한다. 그리고 p가 NULL이 아니면 alloc_perturb함수를 실행하고 주소를 반환한다. 여기서 alloc_pertrub 함수는 할당된 메모리 값을 무작위로 채우는 함수이다. 이러한 이유는 할당된 메모리에 민감한 정보가 있을 수 있기 때문이다.
nb(요청한 size_header) 가 fastbin에 포함되는 크기일 경우...
idx에 fastbin에서 nb크기의 index를 저장한다
fastbin 배열의 인덱스의 첫 번째 chunk의 주소를 pp에 저장한다.
victim에 pp를 저장하고 victim이 NULL인지 판단하고 NULL일 경우는 알맞은 free chunk가 없는 경우이니 break한다.
catomic_compare_and_exchange_val_acq는 여러 스레드가 접근했을 때 불일치 등의 문제를 해결하기 위해 존재한다. 우선 fb와 victim을 비교하고 같다면 fb를 pp에 반환하고 fb는 victim의 fd로 업데이트 한다.
할당 가능한 chunk(victim)을 찾은 후 할당을 요청한 크기(nb)와 일치하는 검사한다. 그리고 check_remalloced_chunk 함수를 호출하여 이전에 할당된 적이 있는지 확인하고, chunk2mem 함수를 사용하여 할당된 메모리 영역의 시작 주소를 계산한다. 그리고 alloc_perturb 함수로 메모리 초기화 수 주소를 반환한다.
nb가 smallbin_range에 포함되면...
idx에 해당 크기의 smallbin 인덱스를 저장
bin에 av→bin의 idx에 해당하는 small bin 주소 저장
victim에 bin의 마지막 chunk를 저장
만약 last(bin)이 null이여서 victim이 0이면 malloc함수가 최초 실행
victim이 bin이면 해당 bin은 비어있는 것
victim이 0이면 malloc_consolidate로 fastbin 병합한다.
__glibc_unlikely로 자기 자신이 victim이 아닐경우 에러출력후 errout
set_inuse_bit_at_offset으로 다음 chunk의 inuse flag를 1로 set
bin→bk = bck; ⇒ bin의 bk chunk를 victim→bk로 설정
bck→fd = bin; ⇒ victim→bk→fd를 bin으로 설정
위 2줄은 bin list에서 victim을 제거하는 과정이다.
av가 main_arena가 아니면...
victim에 NON_MAIN_ARENA flag 설정
check_malloced_chunk 함수를 호출하여 할당된 메모리 블록이 올바르게 처리되었는지 체크.
chunk2mem 함수를 이용하여 victim 블록에 대응하는 메모리 주소를 계산
alloc_perturb 함수를 실행 후 p를 return한다.
small bin이 아니고 largebin인 경우...
av에 fastchunk가 있으면..
malloc_consolidate로 fastbin 병합
unsorted bin list의 bk chunk를 victim에 저장한다.
bck에는 bk chunk의 bk를 저장한다.
victim의 size가 특정 범위를 벗어나면 에러출력을 한다
size에는 flag를 제외한 chunksize를 저장한다.
요청한 크기가 smallbin 사이즈이고, 현재 chunk가 unsortedbin의 유일한 chunk이며, 현재 chunk가 last_remainder이고 size가 요청크기 + 최소크기보다 크다면...
(분할)
우선 해당 chunk를 2개로 나눈다. 한 쪽은 남은 chunk, 한 쪽은 사용할 chunk로 나눈다. 남은 chunk인 remainder는 unsorted bin에 저장하고 last remainder를 remainder로 업데이트 한다. 그리고 remainder의 fd와 bk를 조정해 unsorted_chunk 포인터로 저장한다.
만약 remainder_size가 large bin의 크기라면 fd_nextsize와 bk_nextsize를 초기화한다.
victim->size에 nb, prev_INUSE, NON_MAIN_ARENA 값을 알맞게 set한다.
remainder의 물리적 다음 chunk의 prev_size를 remainder_size로 set한다.
할당된 chunk 주소 리턴한다.
chunk를 unlink 함
요청한 size와 victim의 크기가 같으면...
victim의 다음 chunk의 prev_inuse flag를 set 한다.
main_arena가 아니면 victim의 다음 chunk의 NON_MAIN_ARENA flag set 한다.
할당된 chunk 주소 리턴한다.
(알맞지 않은 chunk는 bin에 넣기 시작)
size가 smallbin 크기라면...
victim_index에 size에 해당하는 smallbin binlist index 저장한다.
binlist에서 index에 해당하는 bin주소를 bck에 저장한다.
fwd은 bck->fd 저장
size가 largebin 크기이면...
bck에는 bin 주소를 저장한다.
fwd에는 bck->fd 저장한다.
binlist 가 비어있지않으면... (fwd != bck)
size에 PREV_INUSE flag를 set한다.
bck->bk->size에 NON_MAIN_ARENA flag가 설정되어있지 않으면 에러 실행(assert 실패)
victim의 크기가 bck->bk->size보다 작을 경우(제일 작은 chunk보다 작음)
victim을 해당 double linked list에 삽입한다.(nextsize를 알맞게 조정한다)(제일 작은 chunk이니 그냥 삽입한다.)
victim의 크기가 bck->bk->size보다 클 경우에는...(애매한 크기이니 알맞은 위치에 삽입해야한다.)
우선 assert로 fwd->size에 NON_MAIN flag가 설정되어있으면 종료한다.
victim의 size가 fwd->size 보다 같거나 클 때 까지 반복한다.
fwd 는 fwd->fd_nextsize로 바뀐다. (제일 큰 chunk부터 fd방향으로 가니 점점 작아진다)
assert로 NON_MAIN_ARENA flag 체크를 한다.
victim의 size와 fwd->size가 같다면...(같은 크기의 chunk를 찾음)
fwd에 fwd->fd 저장한다. (nextsize를 소유한 chunk의 바로 뒤(fd)로 감)
같은 크기를 만나지 않으면...
list 중간에 삽입한다.
nextsize를 조정해준다.
bck에 fwd->bk 저장한다.
largebin이 비어있으면...
fd_nextsize, bk_nextsize를 자기자신으로 한다.
결과적으로는
[bck] [victim] [fwd] 이렇게 된다.
그러면 fd 와 bk를 연결해준다.
이 과정(unsorted bin탐색)을 10000회 반복한다.
요청한 크기 nb 가 largebin 크기라면...
bin에 해당 크기의 index를 저장한다.
largebin이 비어있지 않고, largebin의 첫번째 chunk가(가장 큰 chunk) nb보다 크거나 같으면...
victim에 크기가 가장 작은 chunk를 저장하고
victim의 크기가 요청한 크기보다 커질 때 까지 victim을 다음 chunk로 바꾸는 작업을 반복하여 적절한 chunk를 찾는다.
(제일 작은 chunk부터 탐색)
적절한 chunk가 large bin의 마지막 chunk가 아니고 victim->fd의 size와 victim의 size가 같으면 victim을 victim->fd로 업데이트한다.(재사용을 할 때는 nextsize를 소유한 chunk의 바로 뒤에(fd) chunk 를 사용한다.)
remainder_size에 size - nb 를 저장한다.
largebin에서 victim을 unlink 한다.
만약 remainder_size가 MINSIZE보다 작으면...
victim의 다음 chunk의 PREV_INUSE flag 를 1로 set한다.
만약 victim이 NON_MAIN_ARENA이면 NON_MAIN_ARENA flag를 set한다.
remainder_size가 MINSIZE보다 같거나 크면...
remainder에 remainder_chunk의 주소를 저장하고
bck에는 unsorted bin의 주소를 저장한다.
fwd에는 unsorted bin->fd 를 저장한다.
만약 bck->fd->bk != bck 일 경우 오류 출력
remainder를 unsorted bin 맨 앞에 추가한다.
remainder_size가 largebin보다 크면 nextsize 초기화한다.
split된 victim의 PREV_INUSE, NON_MAIN_ARENA flag를 set한다.
remainder의 flag를 set한다.
할당된 chunk 주소 리턴
idx는 bin list의 인덱스를 계산하는데 사용한다.
idx2block은 idx를 기반으로 bin리스트가 속한 메모리 블록의 인덱스를 계산한다.
map은 bit 변수들이 모인 배열, 각 원소는 각 bit 변수를 가리킨다.
bit는 특정한 크기 범위의 chunk들이 free인지 여부를 비트맵 형태로 나타낸다.
이걸로 bin리스트에 빈 메모리 블록이 있는지 확인한다.
bit 가 1이면 사용중인 chunk를 나타내고 bit 가 0이면 비어있는 chunk를 나타낸다.
bit가 map보다 크거나(bit index 초과), bit가 0 일 경우...
해당 크기에 대한 비어있는 chunk가 없으니 bin을 검색한다. 우선 block을 1 증가시키고 BINMAPSIZE보다 크거나 같아지면 빈 공간이 없으니 use_top 레이블로 점프한다. 반복조건은 우선 binmap[block]으로 값을 가져와 0인지 확인한다. map이 0이면 이전 bin에서도 free된 chunk가 없으으로 계속 다음 bin을 찾는다.
(사용 가능한 chunk를 찾음)
현재 탐색중인 bin의 map에서 해당하는 bit가 1로 설정되어 있는지 체크한다.
즉 bin을 이동하며 bit 위치를 하나씩 이동시켜 1로 설정된 bit를 찾을때까지 반복한다.
찾으면 해당 bin의 chunk를 사용한다.
선택된 bin에서 chunk를 가져오려 하는데 bin이 비어있으면(fasle alarm) bit를 0으로 바꾼다.
그게 아니면 진짜 쓸만한 chunk를 찾은 것
size에는 victim의 size로 하고 remainder에 size->nb 로 나머지를 저장, unlink해준다.
만약 remainder_size < MINSIZE 이면
set_inuse_bit_at_offset 해주고
만약 NON_MAIN_ARENA이면
NON_MAIN_ARENA set 도 해준다.
remainder에 나머지의 주소를 넣는다.
bck에 unsorted bin의 주소를 넣고 fwd에 bck->fd 넣는다.
만약 fwd->bk != bck 이면
errstr 출력하고, errout 실행한다.
remainder의 fd, bk를 연결한다.
만약 요청한 크기가 small크기이면
last_remainder = remainder 로 한다.
만약 remainder_size가 large이면
nextsize 초기화해준다.
set_head와 set_foot 해준다.
사용할 chunk의 주소 return 한다.
use_top 레이블이다.
victim에 해당 arena의 top chunk의 포인터를 저장한다.
size에는 victim 즉 top chunk의 size를 저장한다.
만약 top chunk size가 요구한 size + MINSIZE 보다 크거나 같으면...
remainder_size에 size - nb 넣고
remainder에는 remainder_chunk의 주소를 넣고
top에다가 remainder를 넣는다.
set_head해주고 할당된 chunk의 주소 리턴한다.
만약 현재 arena의 malloc_state에 FASTCHUNK_BIT가 설정되어 있으면...
fast bin 병합하고
만만약 요청한 크기가 small이면
idx에 smallbin index를 저장한다.
아니면(large이면)
idx에 largebin index를 저장한다.
그것도 아니면...
sysmalloc을 통해 메모리를 할당한다.
만약 p != NULL이면
alloc_pertrub로 할당된 메모리 초기화한다.
chunk 주소를 리턴한다.
<틀린 부분이 있다면 비난과 욕설을 해주세요>
'포너블 > Heap' 카테고리의 다른 글
| malloc 소스코드 분석(libc 2.27) (0) | 2023.08.23 |
|---|---|
| free 소스코드 분석(libc 2.23) (0) | 2023.08.16 |
| heap의 개념-(4) (0) | 2023.07.23 |
| heap의 개념-(3) (0) | 2023.07.10 |
| Heap의 개념-(2) (4) | 2023.07.06 |
