malloc.c
- _int_malloc
//_int_malloc
if (!checked_request2size (bytes, &nb))
{
__set_errno (ENOMEM);
return NULL;
}
nb는 패딩 처리가 된 사이즈로 실제 할당하는 크기로 bytes를 변환하는 과정입니다.
#define request2size(req) \
(((req) + SIZE_SZ + MALLOC_ALIGN_MASK < MINSIZE) ? \
MINSIZE : \
((req) + SIZE_SZ + MALLOC_ALIGN_MASK) & ~MALLOC_ALIGN_MASK)
checked_request2size (size_t req, size_t *sz) __nonnull (1)
{
if (__glibc_unlikely (req > PTRDIFF_MAX))
return false;
*sz = request2size (req);
return true;
}
req가 overflow가 일어났는지 판단해서 일어났다면 false를 return하고 아니면 request2size를 실행하고 true를 return합니다.
request2size 함수는 req를 사용 가능한 size로 만들기 위한 함수입니다.
//_int_malloc
if (__glibc_unlikely (av == NULL))
{
void *p = sysmalloc (nb, av);
if (p != NULL)
alloc_perturb (p, bytes);
return p;
}
사용 가능한 아레나가 없으면 sysmalloc을 이용해서 할당 받는 내용의 코드입니다.
alloc_perturb (char *p, size_t n)
{
if (__glibc_unlikely (perturb_byte))
memset (p, perturb_byte ^ 0xff, n);
}
perturb_byte (M_PERURB를 사용하는 malloc의 tunable한 매개 변수)가 0이 아닌 경우, p 가 가리키는 n bytes를 perturb_byte ^ 0xff로 설정합니다.
- sysmalloc
//sysmalloc
if (av == NULL
|| ((unsigned long) (nb) >= (unsigned long) (mp_.mmap_threshold)
&& (mp_.n_mmaps < mp_.n_mmaps_max)))
{
char *mm;
try_mmap:
if (MALLOC_ALIGNMENT == 2 * SIZE_SZ)
size = ALIGN_UP (nb + SIZE_SZ, pagesize);
else
size = ALIGN_UP (nb + SIZE_SZ + MALLOC_ALIGN_MASK, pagesize);
tried_mmap = true;
if ((unsigned long) (size) > (unsigned long) (nb))
{
mm = (char *) (MMAP (0, size, PROT_READ | PROT_WRITE, 0));
if (mm != MAP_FAILED)
{
if (MALLOC_ALIGNMENT == 2 * SIZE_SZ)
{
assert (((INTERNAL_SIZE_T) chunk2mem (mm) & MALLOC_ALIGN_MASK) == 0);
front_misalign = 0;
}
else
front_misalign = (INTERNAL_SIZE_T) chunk2mem (mm) & MALLOC_ALIGN_MASK;
if (front_misalign > 0)
{
correction = MALLOC_ALIGNMENT - front_misalign;
p = (mchunkptr) (mm + correction);
set_prev_size (p, correction);
set_head (p, (size - correction) | IS_MMAPPED);
}
else
{
p = (mchunkptr) mm;
set_prev_size (p, 0);
set_head (p, size | IS_MMAPPED);
}
int new = atomic_exchange_and_add (&mp_.n_mmaps, 1) + 1;
atomic_max (&mp_.max_n_mmaps, new);
unsigned long sum;
sum = atomic_exchange_and_add (&mp_.mmapped_mem, size) + size;
atomic_max (&mp_.max_mmapped_mem, sum);
check_chunk (av, p);
return chunk2mem (p);
}
}
}
mmap으로 할당하는 사이즈는 mp_.mmap_threshold에 들어갑니다. 요구되는 크기가 mp_.mmap_threshold의 최소보다 크고, mmap으로 할당한 사이즈가 최대보다 작으면 위 코드의 if문 안에 들어갑니다.
크기를 가장 가까운 페이지로 올림합니다. 이 청크의 경우 prev_size 필드를 사용할 수 있는 다음 청크가 없기 때문에 오버 헤드는 일반 청크보다 한 SIZE_SZ 단위 더 큽니다.
map 할당에 성공한다면 추가적인 설정들을 업데이트 해주고 반환합니다.
if (av == NULL)
return 0;
/* Record incoming configuration of top */
old_top = av->top; //예전 탑 청크 저장
old_size = chunksize (old_top);
old_end = (char *) (chunk_at_offset (old_top, old_size));
brk = snd_brk = (char *) (MORECORE_FAILURE);
/*
If not the first time through, we require old_size to be
at least MINSIZE and to have prev_inuse set.
*/
assert ((old_top == initial_top (av) && old_size == 0) ||
((unsigned long) (old_size) >= MINSIZE &&
prev_inuse (old_top) &&
((unsigned long) old_end & (pagesize - 1)) == 0));
//top chunk의 포인터와 사이즈가 정상적인지 확인해줍니다.
/* Precondition: not enough current space to satisfy nb request */
assert ((unsigned long) (old_size) < (unsigned long) (nb + MINSIZE));
if (av != &main_arena)
{
heap_info *old_heap, *heap;
size_t old_heap_size;
/* First try to extend the current heap. */
old_heap = heap_for_ptr (old_top);
old_heap_size = old_heap->size;
if ((long) (MINSIZE + nb - old_size) > 0
&& grow_heap (old_heap, MINSIZE + nb - old_size) == 0) //힙이 확장 가능한 경우
{
av->system_mem += old_heap->size - old_heap_size;
set_head (old_top, (((char *) old_heap + old_heap->size) - (char *) old_top)
| PREV_INUSE);
//av를 갱신함으로 힙을 확장
}
else if ((heap = new_heap (nb + (MINSIZE + sizeof (*heap)), mp_.top_pad)))
{
/* Use a newly allocated heap. */
heap->ar_ptr = av;
heap->prev = old_heap;
av->system_mem += heap->size; //사이즈 갱신
/* Set up the new top. */
top (av) = chunk_at_offset (heap, sizeof (*heap));
set_head (top (av), (heap->size - sizeof (*heap)) | PREV_INUSE);
/* Setup fencepost and free the old top chunk with a multiple of
MALLOC_ALIGNMENT in size. */
/* The fencepost takes at least MINSIZE bytes, because it might
become the top chunk again later. Note that a footer is set
up, too, although the chunk is marked in use. */
old_size = (old_size - MINSIZE) & ~MALLOC_ALIGN_MASK;
//malloc alignment의 배수로
set_head (chunk_at_offset (old_top, old_size + 2 * SIZE_SZ), 0 | PREV_INUSE);
if (old_size >= MINSIZE) //최소 크기보다 oldsize가 큰 경우
{
set_head (chunk_at_offset (old_top, old_size), (2 * SIZE_SZ) | PREV_INUSE);
set_foot (chunk_at_offset (old_top, old_size), (2 * SIZE_SZ));
set_head (old_top, old_size | PREV_INUSE | NON_MAIN_ARENA);
_int_free (av, old_top, 1);
}
else
{
set_head (old_top, (old_size + 2 * SIZE_SZ) | PREV_INUSE);
set_foot (old_top, (old_size + 2 * SIZE_SZ));
}
}
else if (!tried_mmap)
/* We can at least try to use to mmap memory. */
goto try_mmap;
}
우선 현재 사용하고 있는 힙을 확장할 수 있는지 확인해줍니다. 메모리의 크기는 system을 이용해서 할당되어 있기 때문에 av를 갱신해 사이즈를 늘려줍니다. 다른 경우에는 새로운 힙을 할당 받아준 다음에 새로운 top chunk를 설정해준 후에 예전의 topchunk는 malloc_alignment의 배수 크기로 free해줍니다.
else /* av == main_arena */
{ /* Request enough space for nb + pad + overhead */
size = nb + mp_.top_pad + MINSIZE;
//사이즈를 설정해줍니다.
/*
If contiguous, we can subtract out existing space that we hope to
combine with new space. We add it back later only if
we don't actually get contiguous space.
*/
if (contiguous (av))
size -= old_size;
//연속적인 경우에는 예전의 사이즈를 빼주는 작업을 합니다.
/*
Round to a multiple of page size.
If MORECORE is not contiguous, this ensures that we only call it
with whole-page arguments. And if MORECORE is contiguous and
this is not first time through, this preserves page-alignment of
previous calls. Otherwise, we correct to page-align below.
*/
size = ALIGN_UP (size, pagesize);
//페이지 사이즈도 가까운 사이즈로 올림해줍니다.
/*
Don't try to call MORECORE if argument is so big as to appear
negative. Note that since mmap takes size_t arg, it may succeed
below even if we cannot call MORECORE.
*/
if (size > 0)
{
brk = (char *) (MORECORE (size));
//morecore를 sbrk로 설정해준다.
LIBC_PROBE (memory_sbrk_more, 2, brk, size);
}
if (brk != (char *) (MORECORE_FAILURE))
{
/* Call the `morecore' hook if necessary. */
void (*hook) (void) = atomic_forced_read (__after_morecore_hook);
if (__builtin_expect (hook != NULL, 0))
(*hook)();
}
else
{
/*
If have mmap, try using it as a backup when MORECORE fails or
cannot be used. This is worth doing on systems that have "holes" in
address space, so sbrk cannot extend to give contiguous space, but
space is available elsewhere. Note that we ignore mmap max count
and threshold limits, since the space will not be used as a
segregated mmap region.
*/
/* Cannot merge with old top, so add its size back in */
if (contiguous (av))
size = ALIGN_UP (size + old_size, pagesize);
//예전의 top을 병합하지 못하는 경우네는 뒤에 더해줍니다.
/* If we are relying on mmap as backup, then use larger units */
if ((unsigned long) (size) < (unsigned long) (MMAP_AS_MORECORE_SIZE))
size = MMAP_AS_MORECORE_SIZE;
/* Don't try if size wraps around 0 */
if ((unsigned long) (size) > (unsigned long) (nb))
{
char *mbrk = (char *) (MMAP (0, size, PROT_READ | PROT_WRITE, 0));
if (mbrk != MAP_FAILED)
{
//끝을 찾기 위해 다른 sbrk를 호출할 필요도 없고 사용할 수도 없습니다.
/* We do not need, and cannot use, another sbrk call to find end */
brk = mbrk;
snd_brk = brk + size;
/*
Record that we no longer have a contiguous sbrk region.
After the first time mmap is used as backup, we do not
ever rely on contiguous space since this could incorrectly
bridge regions.
*/
set_noncontiguous (av);
//연속적인 공간을 신경 쓸 필요가 없습니다.
}
}
}
if (brk != (char *) (MORECORE_FAILURE))
{
if (mp_.sbrk_base == 0)
mp_.sbrk_base = brk;
av->system_mem += size;
/*
If MORECORE extends previous space, we can likewise extend top size.
*/
if (brk == old_end && snd_brk == (char *) (MORECORE_FAILURE))
set_head (old_top, (size + old_size) | PREV_INUSE);
//현재의 공간 내에서 top chunk의 사이즈를 늘릴 수 있습니다.
else if (contiguous (av) && old_size && brk < old_end)
/* Oops! Someone else killed our space.. Can't touch anything. */
malloc_printerr ("break adjusted to free malloc space");
//설정한 공간과 다른 경우 오류 발생
/*
Otherwise, make adjustments:
* If the first time through or noncontiguous, we need to call sbrk
just to find out where the end of memory lies.
* We need to ensure that all returned chunks from malloc will meet
MALLOC_ALIGNMENT
* If there was an intervening foreign sbrk, we need to adjust sbrk
request size to account for fact that we will not be able to
combine new space with existing space in old_top.
* Almost all systems internally allocate whole pages at a time, in
which case we might as well use the whole last page of request.
So we allocate enough more memory to hit a page boundary now,
which in turn causes future contiguous calls to page-align.
*/
else
{
front_misalign = 0;
end_misalign = 0;
correction = 0;
aligned_brk = brk;
/* handle contiguous cases */
if (contiguous (av)) //연속적인 경우
{
/* Count foreign sbrk as system_mem. */
if (old_size)
av->system_mem += brk - old_end;
//외부 sbrk가 어디까지 메모리를 침범했는지 검사해주는 작업
/* Guarantee alignment of first new chunk made from this space */
front_misalign = (INTERNAL_SIZE_T) chunk2mem (brk) & MALLOC_ALIGN_MASK;
if (front_misalign > 0)
{
/*
Skip over some bytes to arrive at an aligned position.
We don't need to specially mark these wasted front bytes.
They will never be accessed anyway because
prev_inuse of av->top (and any chunk created from its start)
is always true after initialization.
*/
correction = MALLOC_ALIGNMENT - front_misalign;
aligned_brk += correction;
//메모리 정렬
}
/*
If this isn't adjacent to existing space, then we will not
be able to merge with old_top space, so must add to 2nd request.
*/
correction += old_size;
/* Extend the end address to hit a page boundary */
end_misalign = (INTERNAL_SIZE_T) (brk + size + correction);
correction += (ALIGN_UP (end_misalign, pagesize)) - end_misalign;
assert (correction >= 0);
snd_brk = (char *) (MORECORE (correction));
/*
If can't allocate correction, try to at least find out current
brk. It might be enough to proceed without failing.
Note that if second sbrk did NOT fail, we assume that space
is contiguous with first sbrk. This is a safe assumption unless
program is multithreaded but doesn't use locks and a foreign sbrk
occurred between our first and second calls.
*/
if (snd_brk == (char *) (MORECORE_FAILURE))
{
correction = 0;
snd_brk = (char *) (MORECORE (0));
}
else
{
/* Call the `morecore' hook if necessary. */
void (*hook) (void) = atomic_forced_read (__after_morecore_hook);
if (__builtin_expect (hook != NULL, 0))
(*hook)();
}
}
/* handle non-contiguous cases */
else //연속적이지 않은 경우
{
if (MALLOC_ALIGNMENT == 2 * SIZE_SZ)
/* MORECORE/mmap must correctly align */
assert (((unsigned long) chunk2mem (brk) & MALLOC_ALIGN_MASK) == 0);
else
{
front_misalign = (INTERNAL_SIZE_T) chunk2mem (brk) & MALLOC_ALIGN_MASK;
if (front_misalign > 0)
{
/*
Skip over some bytes to arrive at an aligned position.
We don't need to specially mark these wasted front bytes.
They will never be accessed anyway because
prev_inuse of av->top (and any chunk created from its start)
is always true after initialization.
*/
aligned_brk += MALLOC_ALIGNMENT - front_misalign;
}
}
/* Find out current end of memory */
if (snd_brk == (char *) (MORECORE_FAILURE))
{
snd_brk = (char *) (MORECORE (0));
}
}
/* Adjust top based on results of second sbrk */
if (snd_brk != (char *) (MORECORE_FAILURE))
//top chunk 설정
{
av->top = (mchunkptr) aligned_brk;
set_head (av->top, (snd_brk - aligned_brk + correction) | PREV_INUSE);
av->system_mem += correction;
/*
If not the first time through, we either have a
gap due to foreign sbrk or a non-contiguous region. Insert a
double fencepost at old_top to prevent consolidation with space
we don't own. These fenceposts are artificial chunks that are
marked as inuse and are in any case too small to use. We need
two to make sizes and alignments work out.
*/
if (old_size != 0)
{
/*
Shrink old_top to insert fenceposts, keeping size a
multiple of MALLOC_ALIGNMENT. We know there is at least
enough space in old_top to do this.
*/
old_size = (old_size - 4 * SIZE_SZ) & ~MALLOC_ALIGN_MASK;
set_head (old_top, old_size | PREV_INUSE);
/*
Note that the following assignments completely overwrite
old_top when old_size was previously MINSIZE. This is
intentional. We need the fencepost, even if old_top otherwise gets
lost.
*/
set_head (chunk_at_offset (old_top, old_size),
(2 * SIZE_SZ) | PREV_INUSE);
set_head (chunk_at_offset (old_top, old_size + 2 * SIZE_SZ),
(2 * SIZE_SZ) | PREV_INUSE);
/* If possible, release the rest. */
if (old_size >= MINSIZE)
{
_int_free (av, old_top, 1);
}
}
}
}
}
} /* if (av != &main_arena) */
if ((unsigned long) av->system_mem > (unsigned long) (av->max_system_mem))
av->max_system_mem = av->system_mem;
check_malloc_state (av);
/* finally, do the allocation */
p = av->top;
size = chunksize (p);
/* check that one of the above allocation paths succeeded */
if ((unsigned long) (size) >= (unsigned long) (nb + MINSIZE))
{
remainder_size = size - nb;
remainder = chunk_at_offset (p, nb);
av->top = remainder;
set_head (p, nb | PREV_INUSE | (av != &main_arena ? NON_MAIN_ARENA : 0));
set_head (remainder, remainder_size | PREV_INUSE);
check_malloced_chunk (av, p, nb);
return chunk2mem (p);
}
/* catch all failure paths */
__set_errno (ENOMEM);
return 0;
}
위의 코드들은 정확히는 이해하지 못하였지만 메모리가 연속적인지 아닌지를 검사해서 만약 연속적인 경우에 대해서는 새로운 공간에 topchunk를 할당합니다. 메모리가 불연속적이거나 sbrk를 사용한 경우에는 사용되고 있는 메모리에 대해서 정렬 단위인 16으로 맞춰주는 작업을 진행하고 top chunk를 설정해줍니다.
- fastbin
//_int_malloc
if ((unsigned long) (nb) <= (unsigned long) (get_max_fast ()))
{
idx = fastbin_index (nb);
mfastbinptr *fb = &fastbin (av, idx);
mchunkptr pp;
victim = *fb; //fastbin의 첫번째 청크
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); //unlink 과정
else
REMOVE_FB (fb, pp, victim); //fastbin 초기화
if (__glibc_likely (victim != NULL)) //victim이 NULL이 아닐 때
{
size_t victim_idx = fastbin_index (chunksize (victim));
//victim의 사이즈를 가진 idx
if (__builtin_expect (victim_idx != idx, 0))
//꺼내온 청크와 할당된 청크의 크기가 다를 경우
malloc_printerr ("malloc(): memory corruption (fast)");
check_remalloced_chunk (av, victim, nb);
#if USE_TCACHE //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); //tcache의 index를 가져온다
if (tcache && tc_idx < mp_.tcache_bins)
//index가 올바르게 들어가 있고, tcache가 있는 경우
{
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
void *p = chunk2mem (victim);
alloc_perturb (p, bytes); //테스트 기능
return p;
}
}
}
nb가 get_max_fast()보다 작은 경우에 위의 if문으로 들어가게 됩니다. (0x80)
nb의 사이즈를 통해 몇 번째 bin인지를 판단해 idx 변수에 넣어줍니다.
#define fastbin_index(sz) \
((((unsigned int) (sz)) >> (SIZE_SZ == 8 ? 4 : 3)) - 2)
#define fastbin(ar_ptr, idx) ((ar_ptr)->fastbinsY[idx])
아레나에서 idx번째에 해당하는 fastbin을 가져옵니다.
fastbin의 첫 번째 청크가 존재하는지 검사하고 존재할 때 스레드가 여러 개라면 REMOVE_FB를 실행하고 스레드가 한 개라면 “*fb = REVEAL_PTR (victim->fd);”를 통해 fastbin[index]에 victim의 다음 청크를 넣어줍니다. 일종의 unlink 과정입니다.
#define REMOVE_FB(fb, victim, pp) \
do \
{ \
victim = pp; \
if (victim == NULL) \
break; \
pp = REVEAL_PTR (victim->fd); \
if (__glibc_unlikely (pp != NULL && misaligned_chunk (pp))) \
malloc_printerr ("malloc(): unaligned fastbin chunk detected"); \
} \
while ((pp = catomic_compare_and_exchange_val_acq (fb, pp, victim)) \
!= victim); \
REMOVE_FB는 fastbin을 초기화할 때 사용하는 함수입니다.
victim의 사이즈와 할당 받아야하는 사이즈의 크기가 다른지도 검사합니다.
check_remalloced_chunk (av, victim, nb);
do_check_remalloced_chunk (mstate av, mchunkptr p, INTERNAL_SIZE_T s)
{
INTERNAL_SIZE_T sz = chunksize_nomask (p) & ~(PREV_INUSE | NON_MAIN_ARENA);
if (!chunk_is_mmapped (p))
{
assert (av == arena_for_chunk (p));
if (chunk_main_arena (p))
assert (av == &main_arena);
else
assert (av != &main_arena);
}
do_check_inuse_chunk (av, p);
/* Legal size ... */
assert ((sz & MALLOC_ALIGN_MASK) == 0);
assert ((unsigned long) (sz) >= MINSIZE);
/* ... and alignment */
assert (aligned_OK (chunk2mem (p)));
/* chunk is less than MINSIZE more than request */
assert ((long) (sz) - (long) (s) >= 0);
assert ((long) (sz) - (long) (s + MINSIZE) < 0);
}
청크가 제대로 할당 되었는지 확인해주는 함수입니다. p→mchunck_size & IS_MAPPED가 false가 나온다면 오류를 출력합니다. (map된 청크는 next와 prev가 존재하지 않습니다.)
청크의 사이즈가 제대로 할당되었는지도 확인해줍니다.
tcache를 사용하는 경우에는 tcache의 index를 가져옵니다. (index가 정확하고 tcache가 있는지도 검사함)
tcache는 하나의 tcache에 7개의 청크만 가질 수 있으므로 tcache가 가득 차거나 fastbin이 비어있기 전까지 fastbin의 청크들을 tcahe에 넣어줍니다.
#define chunk2mem(p) ((void*)((char*)(p) + 2*SIZE_SZ))
사용자에게 전달할 수 있는 주소 형태로 변환해주고 반환합니다.
- smallbin
if (in_smallbin_range (nb)) //small bin의 영역에 있는 경우
{
idx = smallbin_index (nb);
bin = bin_at (av, idx);
if ((victim = last (bin)) != bin) //비어있는 bin이 아닌 경우
{
bck = victim->bk; //head
if (__glibc_unlikely (bck->fd != victim))
malloc_printerr ("malloc(): smallbin double linked list corrupted");
set_inuse_bit_at_offset (victim, nb); //다음 청크의 prev_inuse비트를 활성화
bin->bk = bck;
bck->fd = bin; //unlink 과정
if (av != &main_arena)
set_non_main_arena (victim);
check_malloced_chunk (av, victim, nb);
#if USE_TCACHE //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); //tcahce index
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); //tcache이므로 inuse bit 설정
if (av != &main_arena)
set_non_main_arena (tc_victim);
bin->bk = bck;
bck->fd = bin;
tcache_put (tc_victim, tc_idx);
}
}
}
#endif
void *p = chunk2mem (victim);
alloc_perturb (p, bytes);
return p;
}
}
smallbin range에 있으면 위의 if문에 들어오게 됩니다. (0x000~0x400)
#define smallbin_index(sz) \
((SMALLBIN_WIDTH == 16 ? (((unsigned) (sz)) >> 4) : (((unsigned) (sz)) >> 3))\
+ SMALLBIN_CORRECTION)
smallbin_idx를 통해 index를 구합니다.
bin_at 함수를 통해서 idx에 따른 bin의 주소를 가져옵니다.
lastbin()은 해당 청크의 bk를 리턴하는데 smallbin은 원형이중연결리스트에 FIFO 방식을 사용하기 때문에 이와 같은 코드를 가지고 있습니다.
그리고 이중연결리스트이므로 unlink 과정도 해줍니다.
check_malloced_chunk (av, victim, nb);를 통해 청크가 제대로 할당되었는지도 체크해줍니다.
tcache를 사용하는 경우에는 할당 사이즈에 해당하는 tcache index를 구합니다.
다음은 smallbin의 청크들 중에 tcache에 들어갈 수 있다면 그 청크를 tcache에 넣어주는 작업입니다. 이때도 먼저 넣은 청크를 먼저 빼는 방식으로 마지막 청크순으로 tcache에 넣어줍니다.
그리고 사용자에게 줄 수 있게 가공해서 return합니다.
else
{
idx = largebin_index (nb);
if (atomic_load_relaxed (&av->have_fastchunks))
malloc_consolidate (av);
}
smallbin if문에 들어오지 못한 경우에는 위의 코드가 실행됩니다.
largebin_index를 가져옵니다.
fastchunk들이 존재하는 경우에는 malloc_consolidate() 함수를 실행합니다.
static void malloc_consolidate(mstate av)
{
mfastbinptr* fb; /* current fastbin being consolidated */
mfastbinptr* maxfb; /* last fastbin (for loop control) */
mchunkptr p; /* current chunk being consolidated */
mchunkptr nextp; /* next chunk to consolidate */
mchunkptr unsorted_bin; /* bin header */
mchunkptr first_unsorted; /* chunk to link to */
/* These have same use as in free() */
mchunkptr nextchunk;
INTERNAL_SIZE_T size;
INTERNAL_SIZE_T nextsize;
INTERNAL_SIZE_T prevsize;
int nextinuse;
atomic_store_relaxed (&av->have_fastchunks, false);
unsorted_bin = unsorted_chunks(av); //unsorted bin header 저장
maxfb = &fastbin (av, NFASTBINS - 1); //fastbin 최대 bin list 주소
fb = &fastbin (av, 0); //fastbin 최소 bin list 주소
do { //fb가 maxfb가 될 때까지
p = atomic_exchange_acq (fb, NULL);
if (p != 0) {
do { //해당 fastbin(fb)에서 모든 청크가 소모될 때까지
{
if (__glibc_unlikely (misaligned_chunk (p)))
malloc_printerr ("malloc_consolidate(): "
"unaligned fastbin chunk detected");
unsigned int idx = fastbin_index (chunksize (p));
if ((&fastbin (av, idx)) != fb)
malloc_printerr ("malloc_consolidate(): invalid chunk size");
}
check_inuse_chunk(av, p);
nextp = REVEAL_PTR (p->fd); //next chunk 저장
/* Slightly streamlined version of consolidation code in free() */
size = chunksize (p);
nextchunk = chunk_at_offset(p, size); //물리적으로 nextchunk 저장
nextsize = chunksize(nextchunk); //nextchunk의 사이즈
if (!prev_inuse(p)) { //prev chunk가 free chunk인 경우
prevsize = prev_size (p);
size += prevsize; //청크 병합
p = chunk_at_offset(p, -((long) prevsize)); //p에 prev chunk의 offset 저장
if (__glibc_unlikely (chunksize(p) != prevsize))
malloc_printerr ("corrupted size vs. prev_size in fastbins");
unlink_chunk (av, p); //unlink 과정
}
if (nextchunk != av->top) { //next chunk가 top chunk가 아닌 경우
nextinuse = inuse_bit_at_offset(nextchunk, nextsize); //사용 중인지 확인
if (!nextinuse) { //사용 중이지 않은 청크인 경우
size += nextsize;
unlink_chunk (av, nextchunk); //next chunk를 list에서 제거
} else
clear_inuse_bit_at_offset(nextchunk, 0);
//unsorted bin의 앞의 부분에 새로운 청크 하나를 만드는 과정
first_unsorted = unsorted_bin->fd;
unsorted_bin->fd = p;
first_unsorted->bk = p;
if (!in_smallbin_range (size)) {
p->fd_nextsize = NULL;
p->bk_nextsize = NULL;
}
set_head(p, size | PREV_INUSE); //이전 청크는 사용 중이므로 inuse
p->bk = unsorted_bin;
p->fd = first_unsorted;
set_foot(p, size); //병합한 청크의 size를 nextchunk의 prev_size에 저장
}
else { //next chunk가 top chunk인 경우에는 top chunk와 병합
size += nextsize;
set_head(p, size | PREV_INUSE);
av->top = p;
}
} while ( (p = nextp) != 0);
}
} while (fb++ != maxfb);
}
위의 함수를 코드를 살펴보면 fastbin에 있는 모든 free된 청크들 중 병합할 수 있는 것들은 병합하여 unsortedbin의 head에 추가해주는 작업입니다.
for (;; )
{
int iters = 0;
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 <= 2 * SIZE_SZ)
|| __glibc_unlikely (size > av->system_mem))
malloc_printerr ("malloc(): invalid size (unsorted)");
if (__glibc_unlikely (chunksize_nomask (next) < 2 * SIZE_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)");
for문은 무한반복이고, while문은 unsorted bin에 chunk가 있으면 계속 돌아갑니다. bck은 unsorted bin에 가장 처음 들어간 청크를 가르키고, next는 그 다음 청크가 있습니다.
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;
}
smallbin range에 있고, 할당 받는 크기가 size가 보다 작은 경우에 위의 if문 코드가 실행됩니다. (last remainder가 unsorted bin에 남은 마지막 청크인 경우)
remainder_size에 nb를 빼어 청크를 분할해줍니다.
만약 smallbinrange가 아니라면 fd_nextsize와 bk_nextsize를 설정해줍니다. (largebin)
그 후에 victim을 반환하기 위한 작업을 해주고, 사용자에게 넘기기 위해 메모리 형식으로 처리하고 return합니다.
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을 unsorted bin에서 삭제합니다.
할당하는 사이즈와 unsortedbin에서 가장 앞에 있는 것의 사이즈가 같은 경우에는 우선 요청한 크기가 tcache size이면 victim을 tcache에 넣고 반복문으로 돌아와 return합니다.
if (in_smallbin_range (size)) //small bin 영역인 경우
{
victim_index = smallbin_index (size); //index
bck = bin_at (av, victim_index);
fwd = bck->fd; //첫번째 청크
}
else
{ //largebin 영역인 경우
victim_index = largebin_index (size);
bck = bin_at (av, victim_index);
fwd = bck->fd; //첫번째 청크
/* maintain large bins in sorted order */
if (fwd != bck) //largebin 안에 값이 존재한다면
{
/* 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;
//가장 앞에 새로운 청크 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; //size가 동일한 경우
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 //추가하려고 하는 largebin에 아무런 청크가 없는 경우
victim->fd_nextsize = victim->bk_nextsize = victim;
}
mark_bin (av, victim_index);
victim->bk = bck;
victim->fd = fwd;
fwd->bk = victim;
bck->fd = victim;
//bck와 fd 사이에 victim을 추가
size가 smallbin 범위라면 bin 주소를 구합니다. (tcache에 들어가지 못한 경우)
smallbin의 범위가 아닌 경우에도 마찬가지로 진행합니다. 그리고 구한 largebin 안에 청크가 들어있다면 size와 bck→bk의 크기를 비교합니다. victim size가 largebin에서 가장 작은 size보다 작은 경우에는 fd_nextsize, bk_nextsize에 victim chunk로 설정해줍니다. 아닌 경우에는 size보다 사이즈가 큰 청크 중에 가장 작은 청크가 나올 때까지 진행하다가 fd_nextsize, bk_nextsize를 설정해주는 작업을 진행합니다.
그리고 victim을 fwd와 bk 사이에 넣어줍니다.
if (!in_smallbin_range (nb)) //largebin 영역에 속하는 경우
{
bin = bin_at (av, idx); //bin의 주소
/* 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;
//찾은 청크가 할당 받아야하는 사이즈보다 크고 bin에 청크가 있는 경우
remainder_size = size - nb;
unlink_chunk (av, victim); //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); //remainder chunk 선언
/* We cannot assume the unsorted list is empty and therefore
have to perform a complete insert here. */
bck = unsorted_chunks (av);
fwd = bck->fd; //remainder chunk를 unsorted bin의 head에 넣어줌
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가 large bin size라면
{
remainder->fd_nextsize = NULL;
remainder->bk_nextsize = NULL;
} //fd_nextsize, bk_nextsize 초기화
set_head (victim, nb | PREV_INUSE |
(av != &main_arena ? NON_MAIN_ARENA : 0));
set_head (remainder, remainder_size | PREV_INUSE);
//remainder의 앞이 victim이므로 pre_size를 설정한다.
set_foot (remainder, remainder_size);
//remainder는 free 되어있기 때문에 다음 청크의 pre_size를 설정한다.
}
check_malloced_chunk (av, victim, nb);
void *p = chunk2mem (victim); //메모리 형태로 가공
alloc_perturb (p, bytes);
return p;
}
}
!in_smallbin_range (nb)인 경우에는 위의 코드가 실행됩니다. 가장 큰 청크가 할당 받는 사이즈보다 큰 경우에는 가장 작은 크기의 청크를 victim에 저장합니다. 가장 큰 chunk를 가져와 이 size가 요구되는 size보다 큰 경우에 요구되는 chunk보다 큰 chunk 중 가장 작은 chunk를 찾아 unlink해줍니다.
remainder size가 허용되는 가장 작은 사이즈보다 작으면 victim을 return하고, 아니면 2개의 chunk로 나누어 remainder는 unsorted bin에 넣어줍니다. (head에 넣어줌)
++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_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;
}
}
idx를 증가해 다음 bin을 볼 수 있도록 합니다.
idx에 맞는 청크가 free된적이 없거나 bit가 잘못 구해졌을 경우에 false가 됩니다. binmap이 0이면 즉, 청크가 free된 적이 없으면 반복합니다. 만약 만족하는 것이 없는 경우에는 use_top으로 이동합니다.
freechunk가 있는 bin을 구했다면 그 bin에서 가장 size가 작은 chunk를 victim으로 설정합니다. victim을 unlink해줍니다. 만약 bin이 비어 있다면 다음 bin을 가져옵니다.
앞서 진행한 것과 동일하게 victim을 2개의 chunk로 나누는 작업을 진행합니다. remainder size가 최소 크기의 chunk보다 크다면 victim을 2개의 청크로 분리합니다. remainder는 unsorted bin에 넣어줍니다.
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;
}
/* 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); //heap 영역 늘리기
if (p != NULL)
alloc_perturb (p, bytes);
return p;
}
}
}
top chunk를 가져와 분할 가능하다면 분할합니다. 처리가 불가능한 경우에는 할당 받는 크기가 smallbin 영역이라면 fastbin을 병합합니다. 이는 __libc_malloc()에서 재 할당을 요청하면서 chunk가 할당된다고 합니다. fastchunk가 없으면 sysmalloc으로 heap영역을 늘려 반환합니다.
- _int_realloc
_int_realloc(mstate av, mchunkptr oldp, INTERNAL_SIZE_T oldsize,
INTERNAL_SIZE_T nb)
{
mchunkptr newp; /* chunk to return */
INTERNAL_SIZE_T newsize; /* its size */
void* newmem; /* corresponding user mem */
mchunkptr next; /* next contiguous chunk after oldp */
mchunkptr remainder; /* extra space at end of newp */
unsigned long remainder_size; /* its size */
/* oldmem size */
if (__builtin_expect (chunksize_nomask (oldp) <= 2 * SIZE_SZ, 0)
|| __builtin_expect (oldsize >= av->system_mem, 0))
malloc_printerr ("realloc(): invalid old size");
// 존재 불가능 사이즈인지 확인해주는 작업
check_inuse_chunk (av, oldp);
//사용중인 청크인지 확인해주는 작업
/* All callers already filter out mmap'ed chunks. */
assert (!chunk_is_mmapped (oldp));
next = chunk_at_offset (oldp, oldsize); //다음 chunk
INTERNAL_SIZE_T nextsize = chunksize (next);
if (__builtin_expect (chunksize_nomask (next) <= 2 * SIZE_SZ, 0)
|| __builtin_expect (nextsize >= av->system_mem, 0))
malloc_printerr ("realloc(): invalid next size");
//size가 정상적인지 확인
if ((unsigned long) (oldsize) >= (unsigned long) (nb))
{ //사이즈를 줄여야하는 경우
/* already big enough; split below */
newp = oldp;
newsize = oldsize;
}
else //늘려야하는 경우
{
/* Try to expand forward into top */
if (next == av->top &&
(unsigned long) (newsize = oldsize + nextsize) >=
(unsigned long) (nb + MINSIZE)) //top chunk 사용
{
set_head_size (oldp, nb | (av != &main_arena ? NON_MAIN_ARENA : 0));
av->top = chunk_at_offset (oldp, nb);
set_head (av->top, (newsize - nb) | PREV_INUSE);
check_inuse_chunk (av, oldp);
return chunk2mem (oldp);
//2개의 chunk를 병합하고 nb와 나머지로 짜르고 나머지는 다시 top chunk
}
/* Try to expand forward into next chunk; split off remainder below */
else if (next != av->top &&
!inuse (next) &&
(unsigned long) (newsize = oldsize + nextsize) >=
(unsigned long) (nb))
{ //top chunk 아닌 경우
newp = oldp;
unlink_chunk (av, next);
}
/* allocate, copy, free */
입력받은 사이즈와 청크가 정상적인 것들인지 검사해주는 작업을 수행합니다. map되어 있는 청크 인지 검사해줍니다. 다음 청크를 가져와 사이즈가 정상적인지 확인합니다. 만약 realloc을 통해 chunk의 사이즈를 줄여야하는 경우에는 청크를 분할만 하면 됩니다. 그렇지 않은 경우는 next 청크와 현재 청크의 병합합니다. 만약 다음 청크가 top chunk인 경우에는 병합을 하고 분할한 후에 남은 청크는 다시 topchunk로 설정합니다.
else //다음 size를 더해도 작은 경우
{
newmem = _int_malloc (av, nb - MALLOC_ALIGN_MASK); //사이즈를 할당받는다.
if (newmem == 0)
return 0; /* propagate failure */
newp = mem2chunk (newmem);
newsize = chunksize (newp);
/*
Avoid copy if newp is next chunk after oldp.
*/
if (newp == next)
{
newsize += oldsize;
newp = oldp;
} //이게 왜 있는건지 잘 모르겠디만 newp가 next이면 분할을 해줄 생각으로 추정
else
{
memcpy (newmem, chunk2mem (oldp), oldsize - SIZE_SZ); //값 복사
_int_free (av, oldp, 1);
check_inuse_chunk (av, newp);
return chunk2mem (newp);
}
}
}
/* If possible, free extra space in old or extended chunk */
assert ((unsigned long) (newsize) >= (unsigned long) (nb));
remainder_size = newsize - nb;
if (remainder_size < MINSIZE) /* not enough extra to split off */
{
set_head_size (newp, newsize | (av != &main_arena ? NON_MAIN_ARENA : 0));
set_inuse_bit_at_offset (newp, newsize);
} //짜를 수가 없는 경우
else /* split remainder */
{ //분할한 뒤 remainder는 free해주는 작업
remainder = chunk_at_offset (newp, nb);
set_head_size (newp, nb | (av != &main_arena ? NON_MAIN_ARENA : 0));
set_head (remainder, remainder_size | PREV_INUSE |
(av != &main_arena ? NON_MAIN_ARENA : 0));
/* Mark remainder as inuse so free() won't complain */
set_inuse_bit_at_offset (remainder, remainder_size);
_int_free (av, remainder, 1);
}
check_inuse_chunk (av, newp);
return chunk2mem (newp);
}
다음 사이즈를 더해도 할당 받는 사이즈보다 더 작은 경우에는 _int_malloc을 통해 새로운 사이즈를 할당받습니다. 새로 할당 받은 청크가 next 청크인 경우에는 새로 할당 받은 청크와 oldchunk를 더하고 짜를 준비를 합니다. 2개의 청크로 분할하고 remainder는 free해줍니다.
- __libc_calloc
void *
__libc_calloc (size_t n, size_t elem_size)
{
mstate av;
mchunkptr oldtop, p;
INTERNAL_SIZE_T sz, csz, oldtopsize;
void *mem;
unsigned long clearsize;
unsigned long nclears;
INTERNAL_SIZE_T *d;
ptrdiff_t bytes;
if (__glibc_unlikely (__builtin_mul_overflow (n, elem_size, &bytes))) //size 문제
{
__set_errno (ENOMEM);
return NULL;
}
sz = bytes;
void *(*hook) (size_t, const void *) =
atomic_forced_read (__malloc_hook); //__malloc_hock이 호출되어 있으면 호출
if (__builtin_expect (hook != NULL, 0))
{
mem = (*hook)(sz, RETURN_ADDRESS (0));
if (mem == 0)
return 0;
return memset (mem, 0, sz);
}
MAYBE_INIT_TCACHE ();
if (SINGLE_THREAD_P) //단일 스레드인 경우
av = &main_arena;
else
arena_get (av, sz); //사이즈에 맞는 아레나를 가져옵니다.
if (av)
{
/* Check if we hand out the top chunk, in which case there may be no
need to clear. */
#if MORECORE_CLEARS
oldtop = top (av);
oldtopsize = chunksize (top (av)); //oldtop, oldsize 설정
# if MORECORE_CLEARS < 2
/* Only newly allocated memory is guaranteed to be cleared. */
if (av == &main_arena &&
oldtopsize < mp_.sbrk_base + av->max_system_mem - (char *) oldtop)
oldtopsize = (mp_.sbrk_base + av->max_system_mem - (char *) oldtop);
//시스템에게 더 많은 메모리를 요청할 때 top size 조절
# endif
if (av != &main_arena)
{
heap_info *heap = heap_for_ptr (oldtop);
//새로운 힙 영역을 받아옵니다.
if (oldtopsize < (char *) heap + heap->mprotect_size - (char *) oldtop)
oldtopsize = (char *) heap + heap->mprotect_size - (char *) oldtop;
//시스템에게 더 많은 메모리를 요청할 때 top size 조절
}
#endif
}
else
{
/* No usable arenas. */
oldtop = 0;
oldtopsize = 0;
}
mem = _int_malloc (av, sz); // 아레나로부터 새로운 메모리하나를 할당 받습니다.
assert (!mem || chunk_is_mmapped (mem2chunk (mem)) ||
av == arena_for_chunk (mem2chunk (mem)));
if (!SINGLE_THREAD_P)
{
if (mem == 0 && av != NULL)
{
LIBC_PROBE (memory_calloc_retry, 1, sz);
av = arena_get_retry (av, sz);
mem = _int_malloc (av, sz); //잘못 받아온 경우 다시 받아오는 작업
}
if (av != NULL)
__libc_lock_unlock (av->mutex); //접근 가능하게 unlock
}
/* Allocation failed even after a retry. */
if (mem == 0)
return 0;
p = mem2chunk (mem);
/* Two optional cases in which clearing not necessary */
if (chunk_is_mmapped (p))
{
if (__builtin_expect (perturb_byte, 0))
return memset (mem, 0, sz);
return mem; //오류가 없는 경우 반환
}
csz = chunksize (p);
사이즈 문제가 발생한 경우에는 오류를 발생합니다. malloc_hook이 호출되어 있으면 호출해줍니다. 단일 스레드를 사용하는 경우에은 메인 아레나를 사용하고, 아닌 경우에는 사이즈에 맞는 아레나를 가져옵니다. 시스템에게 더 많은 메모리를 요청하는 경우에는 top chunk의 size를 조정해주는 작업을 합니다. av가 main 아레나가 아니라면 새로운 힙영역을 받아오고 이 경우도 마찬가지로 top chunk의 size를 조정해줍니다. 그리고 아레나로부터 새오누 메모리 하나를 받아옵니다. unlock을 해주고 청크가 map 되어있고 오류가 없으면 return해줍니다.
#if MORECORE_CLEARS
if (perturb_byte == 0 && (p == oldtop && csz > oldtopsize))
{
/* clear only the bytes from non-freshly-sbrked memory */
csz = oldtopsize;
}
#endif
/* Unroll clear of <= 36 bytes (72 if 8byte sizes). We know that
contents have an odd number of INTERNAL_SIZE_T-sized words;
minimally 3. */
d = (INTERNAL_SIZE_T *) mem; //메모리의 저장
clearsize = csz - SIZE_SZ; //헤더 부분은 초기화하지 않아도 됨
nclears = clearsize / sizeof (INTERNAL_SIZE_T);
assert (nclears >= 3);
if (nclears > 9)
return memset (d, 0, clearsize);
else
{
*(d + 0) = 0;
*(d + 1) = 0;
*(d + 2) = 0;
if (nclears > 4)
{
*(d + 3) = 0;
*(d + 4) = 0;
if (nclears > 6)
{
*(d + 5) = 0;
*(d + 6) = 0;
if (nclears > 8)
{
*(d + 7) = 0;
*(d + 8) = 0;
}
}
}
}
//null로 초기화하는 과정
return mem;
}
할당한 메모리에서 헤더 부분은 제외한 모든 부분을 null로 초기화해줍니다.
- _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); //free를 진행할 사이즈
/* 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);
#if USE_TCACHE //tcahe를 사용하는 경우
{
size_t tc_idx = csize2tidx (size); //index를 구한다.
if (tcache != NULL && tc_idx < mp_.tcache_bins) //tcache가 null이 아니고 들어갈 수 있으면
{
/* Check to see if it's already in the tcache. */
tcache_entry *e = (tcache_entry *) chunk2mem (p);//tcahce에 이미 있는지 검사한다.
/* 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))
{
tcache_entry *tmp;
LIBC_PROBE (memory_tcache_double_free, 2, e, tc_idx);
for (tmp = tcache->entries[tc_idx];
tmp;
tmp = REVEAL_PTR (tmp->next))
{
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");
//->bk == tcahce arena이면 double free 검사를 진행한다.
/* 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); //tcache가 사용가능하면 바로 넣어준다.
return;
}
}
}
#endif
사이즈 형태에 문제가 있거나 p+size 이전에 p가 존재하는지 확인하여 이상함이 감지되면 종료합니다. (청크 포인터 이슈) tcahe를 사용하는 경우에는 tcache에 값을 추가할 수 있는 경우라면 tcahe에 값을 추가하고 만약 bk가 tcache 아레나에 있는 경우에는 double free 검사를 진행합니다.
if ((unsigned long)(size) <= (unsigned long)(get_max_fast ())
//fastbin에 들어갈 청크인지 확인
#if TRIM_FASTBINS
/*
If TRIM_FASTBINS set, don't place chunks
bordering top into fastbins
*/
&& (chunk_at_offset(p, size) != av->top)
//TRIM_FASTBIN이면 top chunk와 붙어있는 청크가 아니여야한다.
#endif
) {
if (__builtin_expect (chunksize_nomask (chunk_at_offset (p, size))
<= 2 * SIZE_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)) <= 2 * SIZE_SZ
|| chunksize (chunk_at_offset (p, size)) >= av->system_mem);
//크기 검사
__libc_lock_unlock (av->mutex); //잠금을 해제한다.
}
if (fail)
malloc_printerr ("free(): invalid next size (fast)");
}
free_perturb (chunk2mem(p), size - 2 * SIZE_SZ); //초기화
atomic_store_relaxed (&av->have_fastchunks, true);
unsigned int idx = fastbin_index(size); //fastbin index
fb = &fastbin (av, idx);//해당 bin 가져오기
/* Atomically link P to its fastbin: P->FD = *FB; *FB = P; */
mchunkptr old = *fb, old2; //최근에 free한 청크에 저장
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))//최근에 free한 청크와 지금 free할려는 청크가 같음
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)) //단일 스레드가 아닌 경우에도 double free 검사
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);
/* 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)");
}
//최근에 free한 chunk의 사이즈와 지금 free하려는 chunk의 사이즈가 같은지 확인
fastbin에 들어갈 청크이고, 청크의 사이즈 검사를 진행한 후에 초기화 작업을 진행합니다. 할당 받는 사이즈에 따라 fastbin에서 index를 가져옵니다.fastbin에서 가장 최근에 free한 chunk와 지금 free할려는 청크가 동일한지 검사합니다. 만약 동일하면 double free 버그를 발생합니다. 아무런 문제가 없다면 fastbin의 head부분에 청크를 추가해줍니다. fastbin index가 제대로 들어갔는지 검사를 해줍니다.
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)) //top chunk인 경우
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)");
//nextchunk가 쓰이지 않는 경우
nextsize = chunksize(nextchunk);
if (__builtin_expect (chunksize_nomask (nextchunk) <= 2 * SIZE_SZ, 0)
|| __builtin_expect (nextsize >= av->system_mem, 0))
malloc_printerr ("free(): invalid next size (normal)");
//nextchunk의 사이즈가 이상한 경우
free_perturb (chunk2mem(p), size - 2 * SIZE_SZ); //memset을 통해 초기화
/* consolidate backward */
if (!prev_inuse(p)) { //prev chunk가 free chunk인 경우에는 병합
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); //병합된 청크를 unlink
}
if (nextchunk != av->top) {
/* get and clear inuse bit */
nextinuse = inuse_bit_at_offset(nextchunk, nextsize);
/* consolidate forward */
if (!nextinuse) { //nextchunk가 사용 중이지 않은 경우
unlink_chunk (av, nextchunk);
size += nextsize; //청크 병합
} 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); //unsorted bin의 header
fwd = bck->fd; // unsorted bin의 첫번째 청크
if (__glibc_unlikely (fwd->bk != bck)) //아무것도 없는 경우
malloc_printerr ("free(): corrupted unsorted chunks");
p->fd = fwd;
p->bk = bck; //linking
if (!in_smallbin_range(size)) //largebin인 경우
{
p->fd_nextsize = NULL;
p->bk_nextsize = NULL;
}
bck->fd = p;
fwd->bk = p;//unsorted bin의 head에 p를 삽입
set_head(p, size | PREV_INUSE);
set_foot(p, size);
check_free_chunk(av, p); //free가 정상적으로 진행되었는지 확인
}
/*
If the chunk borders the current high end of memory,
consolidate into top
*/
else { //next_chunk가 top인 경우
size += nextsize;
set_head(p, size | PREV_INUSE);
av->top = p;
check_chunk(av, p); //병합을 진행한다.
}
free하는 청크가 map되어있지 않다면 우선 청크가 topchunk인지 아닌지 검사를 진행합니다. 해당 청크의 물리적으로 다음 청크가 아레나에 존재하는지도 검사를 합니다. 또, 다음 청크의 prer_inuse bit가 제대로 있는지에 대한 검사도 수행합니다. 초기화를 해준 다음에는 nextchunk도 free되어 있는 경우에는 next chunk를 unlink해주고, 앞과 다음 청크들을 free하는 청크와 합친 후에 unsorted bin의 head에 넣어줍니다. 그리고 제대로 unsorted bin에 들어갔는지에 대한 검사도 수행합니다. top chunk인 경우에는 top chunk와 병합해줍니다. 아니면 unsorted bin에 들어갑니다.
if ((unsigned long)(size) >= FASTBIN_CONSOLIDATION_THRESHOLD) {
//fastbin의 최대보다 클 때
if (atomic_load_relaxed (&av->have_fastchunks))
malloc_consolidate(av); //fastbin 병합을 진행
if (av == &main_arena) {
#ifndef MORECORE_CANNOT_TRIM
if ((unsigned long)(chunksize(av->top)) >=
(unsigned long)(mp_.trim_threshold))
systrim(mp_.top_pad, av);
//top의 size가 너무 크면 systrim으로 크기를 줄임
#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);
}
/*
If the chunk was allocated via mmap, release via munmap().
*/
else {
munmap_chunk (p);
}
사이즈가 FASTBIN_CONSOLIDATION_THRESHOLD보다 큰 경우에는 malloc_consolidate 함수를 사용하고, top chunk의 사이즈가 trim_threshold보다 큰 경우에는 systrim() 함수를 호출해 크기를 줄입니다. 청크가 map되어 있으면 munmap_chunk를 호출합니다.
systrim (size_t pad, mstate av)
{
long top_size; /* Amount of top-most memory */
long extra; /* Amount to release */
long released; /* Amount actually released */
char *current_brk; /* address returned by pre-check sbrk call */
char *new_brk; /* address returned by post-check sbrk call */
size_t pagesize;
long top_area;
pagesize = GLRO (dl_pagesize);
top_size = chunksize (av->top); //top chunk의 사이즈
top_area = top_size - MINSIZE - 1;
if (top_area <= pad)
return 0;
/* Release in pagesize units and round down to the nearest page. */
extra = ALIGN_DOWN(top_area - pad, pagesize);
//pagesize를 가장 차이가 적게나는 페이지 크기로 만듭니다.
if (extra == 0)
return 0;
/*
Only proceed if end of memory is where we last set it.
This avoids problems if there were foreign sbrk calls.
*/
current_brk = (char *) (MORECORE (0));
if (current_brk == (char *) (av->top) + top_size)
{
/*
Attempt to release memory. We ignore MORECORE return value,
and instead call again to find out where new end of memory is.
This avoids problems if first call releases less than we asked,
of if failure somehow altered brk value. (We could still
encounter problems if it altered brk in some very bad way,
but the only thing we can do is adjust anyway, which will cause
some downstream failure.)
*/
MORECORE (-extra);
/* Call the `morecore' hook if necessary. */
void (*hook) (void) = atomic_forced_read (__after_morecore_hook);
if (__builtin_expect (hook != NULL, 0))
(*hook)();
new_brk = (char *) (MORECORE (0));
LIBC_PROBE (memory_sbrk_less, 2, new_brk, extra);
if (new_brk != (char *) MORECORE_FAILURE)
{
released = (long) (current_brk - new_brk);
if (released != 0)
{
/* Success. Adjust top. */
av->system_mem -= released;
set_head (av->top, (top_size - released) | PREV_INUSE);
check_malloc_state (av);
return 1;
}
}
}
return 0;
}
현재 top chunk의 크기에서 chunk 정보를 저장하기 위한 최소 크기와 top chunk가 기본적으로 가져야 할 여유 공간의 크기를 뺀 크기를 페이지로 조정하고 sbrk를 호출합니다. after_morecore_hook이 있다면 hook을 호출한 뒤 top chunk의 크기를 조절합니다.