Heap - glibc 2.23 (_int_malloc)
_int_malloc
1. _int_malloc
static void *
_int_malloc (mstate av, size_t bytes)
- mstate av : 아레나를 가리키는 포인터이다.
- size_t bytes : 사용자가 malloc(byte)를 통해 요청한 순수한 메모리 크기이다.
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;
요청 및 청크 관련
- nb(normalized bytes) : 사용자 요청 bytes에 헤더 크기와 정렬 패딩을 더한 실제 내부 청크 크기이다.
- victim : bin에서 꺼내온 ‘희생자’, 할당 후보가 되는 청크를 가리키는 포인터이다.
- size : victim의 청크 크기를 임시로 저장한다.
bin 관련
- idx : nb 크기에 해당하는 fastbinsY 또는 bins 배열의 인덱스를 저장한다.
- bin : bins 배열 내의 특정 bin의 헤드를 가리키는 포인터이다.
- victim_index : Unsorted bin에서 청크를 꺼내 정렬할 때, 청크가 들어가야 할 bin의 인덱스를 저장한다.
청크 분할(split) 관련
- remainder : 큰 victim 청크를 nb만큼 잘라내고 남은 나머지 부분을 가리키는 포인터
- remainder_size : remainder 청크의 크기를 저장한다.
binmap 탐색 관련
- block, bit, map : large bin을 탐색할 때 binmap을 효율적으로 순회하기 위한 변수들이다
기타
- fwd, bck : 이중 연결 리스트에서 청크를 연결하거나 해제(unlink)할 때 사용하는 임시 포인터이다.
- errstr : 오류가 발생했을 때 오류 메시지를 저장하기 위한 변수이다.
초기화 및 예외처리 코드
checked_request2size (bytes, nb);
- checked_request2size : 사용자가 요청한 bytes를 내부 청크 크기 nb 로 변환한다.
if (__glibc_unlikely (av == NULL))
{
void *p = sysmalloc (nb, av);
if (p != NULL)
alloc_perturb (p, bytes);
return p;
}
- if (__glibc_unlikely (av == NULL)) : 아레나가 없는 예외 상황을 처리한다.
- sysmalloc (nb, av) : 아레나가 없기 때문에 운영체제로부터 직접 메모리를 가져오는 sysmalloc 함수를 사용한다.
- alloc_perturb (p, bytes) : 할당된 메모리를 특정 패턴으로 채운다.
- return p : sysmalloc이 성공적으로 메모리를 받아오면 그 주소를 반환하고 함수를 종료한다.
fastbin 확인 로직
1. 진입 조건
if ((unsigned long) (nb) <= (unsigned long) (get_max_fast ()))
- checked_request2size를 통해 계산된 내부 청크 크기 nb가 get_max_fast(fastbin이 처리하는 최대 크기) 이하인지 확인한다.
2. fastbin에서 청크 꺼내기
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);
- idx = fastbin_index (nb) : nb 크기에 해당하는 fastbin의 인덱스를 계산한다.
- mfastbinptr *fb = &fastbin (av, idx) : fastbin 리스트의 시작점 주소를 fb에 저장한다.
- do - while : 안전하게 리스트의 첫번째 청크를 꺼내는 로직이다.
- victim = pp : 현재 리스트의 첫 번째 청크를 victim 으로 설정한다.
- if (victim == NULL) : 만약 bin이 비어있다면 victim이 NULL 이므로 즉시 루프를 탈출한다.
- while ((pp = catomic_ …. != victim) : compare_and_exchange 연산을 통해 리스트의 시작점(fb)을 첫 번째 청크의 다음 청크 victim→fb로 바꾸려고 시도한다.
3. 보안 검사
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;
}
- if (victim !=0) : victim 청크를 확보했다면 이 청크가 유효한지 최종적으로 검사한다.
- fastbin_index (chunksize (victim)) != idx : 꺼내온 victim 청크의 크기를 다시 계산하고 이 청크가 원래 있던 bin의 인덱스와 일치하는지 확인한다.
4. 성공 및 반환
check_remalloced_chunk (av, victim, nb);
void *p = chunk2mem (victim);
alloc_perturb (p, bytes);
return p;
}
}
- check_remalloced_chunk : 디버깅용 검사 매크로이다
- void *p = chunk2mem (victim) : 청크의 시작주소 victim에서 헤더 크기만큼 뒤로 이동해서 사용자에게 실제로 돌려줄 메모리 영역의 주소 p를 계산한다.
- alloc_perturb (p, bytes) : 할당된 메모리를 특정 패턴으로 채워넣는다.
- return p : 사용자에게 메모리 주소 p를 반환하고 함수를 종료한다.
smallbin 확인 로직
1. 진입 조건
if (in_smallbin_range (nb))
- nb가 small bin 크기 범위 내에 있는지 확인한다.
2. bin에서 청크 꺼내기
idx = smallbin_index (nb);
bin = bin_at (av, idx);
if ((victim = last (bin)) != bin)
- idx = smallbin_index (nb) : nb 크기에 맞는 smallbin의 인덱스를 계산한다.
- bin = bin_at (av, idx) : 해당 인덱스의 bin 헤드 주소를 bin 포인터에 저장한다.
- if ((victim = last (bin)) != bin) : bin이 비어있지 않은지 확인한다.
- bin이 비어있으면 last(bin)은 bin의 헤드 자신을 반환하기 때문에 victim == bin이 되어 if 블록에 들어가지 않는다.
3. 예외 처리 : 초기화되지 않은 bin
if (victim == 0) /* initialization check */
malloc_consolidate (av);
else
{
bck = victim->bk;
- if (victim == 0) : bin이 초기화되지 않았거나 손상되었을 가능성을 확인한다.
- malloc_consolidate : fastbin을 모두 병합하고 bin이 초기화 되지 않았다면 초기화 한다.
- else : victim이 유효한 청크일 때 실행된다.
- smallbin은 삽입은 헤드 제거는 테일 원칙으로 동작하여 FIFO 처럼 동작한다.
4. 청크 분리 및 반환
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 (__glibc_unlikely (bck->fd != victim)) : 이중 연결 리스트의 무결성을 검사한다.
- set_inuse_bit_at_offset (victim, nb) : victim 청크 바로 다음 청크의 PREV_INUSE 비트를 1로 설정한다.
- bin->bk = bck; bck->fd = bin : victim을 bin에서 분리한다.
- victim->size |= NON_MAIN_ARENA : 쓰레드 아레나 청크일 경우 A 비트를 설정한다.
Unsorted bin 확인 로직
1. 사전 작업
else
{
idx = largebin_index (nb);
if (have_fastchunks (av))
malloc_consolidate (av);
}
- fastbin과 smallbin에서 청크를 찾지 못했고 사용자 요청이 Large 크기일 때 실행된다.
- idx = largebin_index (nb) : Largebin의 인덱스를 미리 계산하여 idx 변수에 저장한다.
- if (have_fastchunks (av)) : FASTCHUNKS_BIT 플래그를 확인하여 아레나에 fastbin 청크가 존재하는지 검사한다.
- malloc_consolidate (av) : fastbin에 청크가 있다면 malloc_consolidate 함수를 호출하여 unsorted bin으로 옮기는 작업을 한다.
2. Unsorted bin 순회 루프 진입
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);
for (;; ) 루프
- 대부분의 경우 한 번만 실행되지만 malloc의 모든 탐색이 실패하여 top chunk마저 부족할 때, malloc_consolidate 한 뒤 탐색을 다시 시작한다. → 이 때 이 루프가 실행된다.
- int iters = 0 : iters 변수는 무한 루프 방지용 카운터이다.
while 루프
- while ((victim = unsorted_chunks (av)->bk) != unsorted_chunks (av))
- unsorted_chunks(av) : unsorted bin의 헤드를 가리킨다.
- ->bk : unsorted bin은 이중 연결 리스트로 이 코드는 리스트의 맨 뒤에서부터 청크를 꺼낸다.
- victim : 꺼내온 변수를 victim에 저장한다.
- != unsorted_chunks (av) : 리스트가 비어있지 않은 동안 루프를 계속 실행한다.
- bck = victim->bk : victim을 리스트에서 제거하기 전에 그 다음 처리할 청크의 주소를 bck에 미리 저장한다.
- if (__builtin_expect … ) : victim 청크의 size 필드가 유효한 범위 내에 있는지 무결성 검사를 한다.
- size = chunksize (victim) : victim 헤더에서 순수한 크기 값을 읽어와 size에 저장한다.
3. last_remainder 확인 (Best fit 처리 로직)
if (in_smallbin_range (nb) &&
bck == unsorted_chunks (av) &&
victim == av->last_remainder &&
(unsigned long) (size) > (unsigned long) (nb + MINSIZE))
{
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;
}
1. 진입 조건
- in_smallbin_range (nb) : 사용자 요청(nb)이 smallbin 크기여야 한다.
- bck == unsorted_chunks (av) : victim이 unsorted bin의 유일한 청크여야 한다.
- victim == av->last_remainder : unsorted bin의 유일한 청크가 last_remainder여야 한다.
- (size) > (nb + MINSIZE) : victim의 size가 nb를 만족시키고도 남는 조각이 MINSIZE이상이 될 만큼 충분히 커야 한다.
2. 청크 분할 및 처리
- remainder_size = size - nb : 요청 크기를 제외한 나머지 부분의 크기를 계산한다.
- remainder = chunk_at_offset (victim, nb) : victim의 시작 주소에서 nb만큼 떨어진 곳을 remainder 청크의 시작점으로 지정한다.
- unsorted_chunks (av)->bk = unsorted_chunks (av)->fd = remainder
- unsorted bin을 비우고 remainder 청크를 unsorted bin의 유일한 청크로 넣는다
- 아레나의 last_remainder 포인터도 새로운 remainder를 가리키도록 업데이트 한다.
- set_head (victim, … ) : 사용자에게 반활될 victim의 헤더는 요청된 크기 nb와 사용 중 플래그를 담아 설정한다.
- set_head, set_foot : remainder는 새로운 free 청크이기 때문에 그 header와 footer에 remainder_size를 기록한다.
4. Exact Fit 처리 로직
unsorted_chunks (av)->bk = bck;
bck->fd = unsorted_chunks (av);
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;
}
1. victim을 unsorted bin에서 분리
- unsorted_chunks (av)->bk = bck : unsorted bin의 헤드가 victim 대신 bck를 가리키게 한다.
- bck->fd = unsorted_chunks (av) : bck가 victim 대신 헤드를 가리키게 한다.
2. Exact fit
- if (size == nb) : size는 victim의 실제 크기로 victim이 nb랑 일치하는지 확인한다.
- set_inuse_bit_at_offset (victim, size) : victim을 사용중으로 표시한다.
- victim->size |= NON_MAIN_ARENA : 만약 쓰레드 아레나라면, victim의 size 필드에 A 비트를 설정한다.
- check_malloced_chunk (av, victim, nb) : 청크의 유효성을 검사한다.
- void *p = chunk2mem (victim) : victim을 사용자에게 반환할 메모리 포인터 p로 변경한다.
5. 목적지 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;
- if (in_smallbin_range (size) : smallbin으로 보낼 경우
- victim_index = smallbin_index (size) : size에 해당하는 smallbin 인덱스를 계산하여 victim_index에 저장한다.
- bck = bin_at (av, victim_index) : bin_at 매크로를 이용해 해당 victim_index에 위치한 bin의 헤드 주소를 가져온다.
- fwd = bck->fd : 해당 bin의 헤드(bck)가 가리키는 첫 번째 청크의 주소를 fwd에 저장한다.
- else : Large bin으로 보낼 경우
- victim_index = largebin_index (size) : size에 해당하는 large bin의 인덱스 번호를 계산하여 victim_index에 저장한다.
- bck = bin_at (av, victim_index) : victim_index에 위치한 bin의 헤드 주소를 bck에 저장한다.
- fwd = bck->fd : 해당 bin의 첫 번째 청크 주소를 fwd에 저장한다.
6. Largebin 정렬 삽입
if (fwd != bck)
{
size |= PREV_INUSE;
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)
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;
}
- if (fwd != bck) : Largebin이 비어있지 않은지 확인한다.
- if ((unsigned long) (size) < (unsigned long) (bck->bk->size)) victim의 크기(size)가 bin의 마지막 청크(bck→bk)보다도 작은지 확인한다.
- victim은 리스트의 맨 뒤가 되고 포인터를 리스트의 끝으로 조정한 뒤 fd_nextsize, bk_nextsize 리스트에도 연결한다.
- else: victim이 중간에 들어가야 하는 경우이다.
- while 루프는 fd_nextsize에서 victim보다 크기가 작거나 같은 청크를 빠르게 찾는다.
- if (size == fwd→size) : 만약 같은 크기의 청크가 있다면 항상 두 번째 위치에 삽입하여 첫 노드를 nextsize 리스트의 앵커로 유지한다.
- else : 다른 크기라면 fwd 앞에 삽입되어야 하기 때문에 fd_nextsize, bk_nextsize 포인터를 정교하게 조작한다.
- bck = fwd->bk : 삽입될 위치의 이전 노드를 bck에 정확히 설정한다.
- if ((unsigned long) (size) < (unsigned long) (bck->bk->size)) victim의 크기(size)가 bin의 마지막 청크(bck→bk)보다도 작은지 확인한다.
- else : largebin이 비어있었다면, victim이 유일한 청크가 되기 때문에 fd_nextsize와 bk_nextsize가 자기 자신을 가리키도록 한다.
더보기
앵커?
앵커는 nextsize 리스트에서 각 크기 그룹을 대표하는 기준점 역할을 하는 첫 번째 청크를 의미한다.
7. 최종 연결 작업
mark_bin (av, victim_index);
victim->bk = bck;
victim->fd = fwd;
fwd->bk = victim;
bck->fd = victim;
- mark_bin (av, victim_index) : victim이 들어갈 bin이 비어있지 않다고 binmap을 1로 표시한다.
- victim->bk = bck; victim->fd = fwd : victim의 포인터들이 자신의 이전 노드(bck)와 다음 노드(fwd)를 가리키게 한다.
- fwd->bk = victim; bck->fd = victim : bck와 fwd가 victim을 가리키게 한다.
8. 무한 루프 방지 장치
#define MAX_ITERS 10000
if (++iters >= MAX_ITERS)
break;
}
- #define MAX_ITERS 10000 : 최대 반복 횟수를 10000으로 정의한다.
- if (++iters >= MAX_ITERS) : 루프의 반복 횟수가 10000에 도달했는지 확인한다.
- break : 반복 횟수가 10000에 도달했다면 while루프를 강제로 탈출한다.
Largebin 탐색 및 분할
large bin에서 malloc은 현재 bin의 가장 큰 청크가 요청보다 큰 지 확인한 후 가장 작은 그룹(bk_nextsize)부터 위로 올라오며 요청 크기(nb) 이상의 최소 청크를 찾는다.
1. 진입 조건
if (!in_smallbin_range (nb))
{
bin = bin_at (av, idx);
if ((victim = first (bin)) != bin &&
(unsigned long) (victim->size) >= (unsigned long) (nb))
- if (!in_smallbin_range (nb)) : nb가 Large chunk 크기일 경우에만 실행된다.
- bin = bin_at (av, idx) : idx를 이용해 nb 크기에 가장 이상적인 largebin의 헤드 주소를 가져온다.
- if ((victim = first (bin)) != bin && (victim→size) ≥ (nb) : 탐색을 하기 전의 사전 검사
- victim = first (bin)) != bin : 해당 bin이 비어있지 않은지 확인한다.
- victim→size ≥ nb : first(bin)은 해당 bin에서 가장 큰 청크를 가리킨다. 가장 큰 청크가 nb보다 작으면 if 문 전체를 건너뛴다.
2. bk_nextsize를 이용한 탐색
victim = victim->bk_nextsize;
while (((unsigned long) (size = chunksize (victim)) <
(unsigned long) (nb)))
victim = victim->bk_nextsize;
- victim = victim->bk_nextsize : large bin은 내림차순으로 정렬되어 있기 때문에 가장 작은 청크부터 탐색하는 것이 효율적이다. bk_nextsize는 가장 작은 크기 그룹의 시작점으로 점프하는 포인터이다.
- while (… ) victim = victim->bk_nextsize : bk_nextsize : bk_nextsize 리스트를 따라 작은 크기에서 큰 크기 그룹으로 올라가며 탐색한다. victim의 크기가 nb보다 크거나 같아지는 순간 루프가 멈춘다.
3. 탐색 후 최적화
if (victim != last (bin) && victim->size == victim->fd->size)
victim = victim->fd;
- victim이 리스트의 기준점이고 바로 뒤에 같은 크기의 청크가 있다면 바로 뒤 청크를 victim으로 선택한다.
4. 청크 분할 또는 전체 사용
remainder_size = size - nb;
unlink (av, victim, bck, fwd);
if (remainder_size < MINSIZE)
{
set_inuse_bit_at_offset (victim, size);
if (av != &main_arena)
victim->size |= NON_MAIN_ARENA;
}
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);
}
- if (remainder_size < MINSIZE) : victim을 nb만큼 잘라내고 남는 조각이 너무 작아서 청크가 될 수 없는경우이다. 낭비를 막기 위해 victim 전체를 사용자에게 할당한다.
- else : 분할하고 남는 조각이 충분히 큰 경우이다.
- remainder = chunk_at_offset (victim, nb) : 남는 조각을 remainder 청크로 만든다.
- bck = unsorted_chunks (av) : remainder 청크를 다시 unsorted bin의 맨 앞에 넣는다.
- set_head (victim, …) : 사용자에게 줄 victim 부분의 헤더 크기를 nb로 수정한다.
- set_head (remainder, …); set_foot (remainder, …) : remainder가 유효한 free 청크가 되도록 헤더와 푸터를 설정한다.
5. 최종 반환
check_malloced_chunk (av, victim, nb);
void *p = chunk2mem (victim);
alloc_perturb (p, bytes);
return p;
- check_malloced_chunk (av, victim, nb) : 할당될 청크의 유효성을 검사한다.
- p = chunk2mem (victim) : 헤더를 제외한 실제 사용자 데이터 영역의 시작 주소를 계산한다.
- alloc_perturb (p, bytes) : 할당된 메모리를 특정 패턴으로 채워넣는다.
- return p : 최종적으로 사용자에게 메모리 포인터 p를 반환한다.
더 큰 Large bin 확인 로직
1. 탐색 준비
++idx;
bin = bin_at (av, idx);
block = idx2block (idx);
map = av->binmap[block];
bit = idx2bit (idx);
- ++idx : largebin에서 청크를 찾지 못했으므로 인덱스를 1 증가시켜서 바로 다음으로 큰 bin부터 탐색을 시작한다.
- binmap 초기화
- block = idx2block (idx) : idx가 binmap 배열의 몇번째 unsigned int에 해당하는지를 계산한다.
- map = av->binmap[block] : 해당 block의 실제 비트값을 map 변수에 저장한다.
- bit = idx2bit (idx) : 현재 idx가 map 내의 몇 번째 비트에 해당하는지 나타내는 비트 마스크를 계산한다.
2. binmap을 이용한 반복 탐색
for (;; )
{
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;
}
- for (;; ) : nb를 만족하는 청크를 찾거나 모든 bin을 다 확인해서 top chunk를 사용해야 할 때까지 계속된다.
- if (bit > map || bit == 0) : 현재 map에서 더 이상 검사할 비트가 없을 때 실행된다.
- do - while 루프 : binmap 배열의 다음 block으로 이동하며 0이 아닌 map을 찾을 때까지 매우 빠르게 스캔한다.
- if (++block >= BINMAPSIZE) : 모든 bin을 다 확인했는데도 bin이 없다면 goto use_top을 통해 top chunk를 사용한다.
- bin = bin_at (av, (block << BINMAPSHIFT)) : map을 찾으면 bin 포인터를 그 그룹의 첫 번째 bin으로 bit 마스크를 첫 번째 비트로 리셋하여 스캔을 준비한다.
- do - while 루프 : binmap 배열의 다음 block으로 이동하며 0이 아닌 map을 찾을 때까지 매우 빠르게 스캔한다.
- if (bit > map || bit == 0) : 현재 map에서 더 이상 검사할 비트가 없을 때 실행된다.
3. block 내에서 비어있지 않은 bin 찾기
while ((bit & map) == 0)
{
bin = next_bin (bin);
bit <<= 1;
assert (bit != 0);
}
- while ((bit & map) == 0) : 비트 연산을 통해 현재 map에서 1로 설정된 비트를 찾을 때까지 bit를 왼쪽으로 시프트 연산을 한다.
- bin 포인터도 다음 bin으로 이동한다.
4. bin 처리 및 반환
/* 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;
}
}
- victim = last (bin) : binmap으로 찾은 비어있지 않은 bin에서 대략적으로 가장 오랫동안 사용되지 않은(LRU, Least Recently Used) 청크를 선택하는 동점 처리(tie-break) 규칙이다.
- if (victim == bin) : binmap 비트와 실제 bin 상태가 일치하지 않는 경우 binmap의 해당 비트를 0으로 수정하고 다음 bin으로 넘어간다.
- else : 사용할 청크를 찾았을 때이다.
- 이후의 로직은 이전에 분석한 Large bin 탐색 및 분할 로직과 동일하다.
Top Chunk 사용
use_top:
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;
}
}
}
- use_top : 요청을 만족하는 free 청크를 전혀 찾지 못했을 때 도달하는 지점이다.
1. Top chunk 분할
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;
}
- if ((unsigned long) (size) >= (unsigned long) (nb + MINSIZE)) : Top chunk의 크기가 요청된 크기 nb와 분할 후 남은 조각이 최소 크기의 합보다 크거나 같은지 확인한다.
- remainder = chunk_at_offset (victim, nb) : 아레나의 top 포인터를 remainder의 시작 주소로 올린다.
- av->top = remainder : 아레나의 top 포인터를 remainder의 시작 주소 위로 올린다.
- set_head (victim, … ) : 사용자에게 반활될 victim의 헤더를 nb 크기로 설정하고 사용 중으로 표시한다.
- set_head (remainder, … ) : 새로운 Top chunk가 된 remainder의 헤더를 남은 크기로 업데이트 한다.
2. 정리 및 재시도
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);
}
- else if (have_fastchunks (av)) : fastbin에만 free청크가 남아있는 경우일 때에 동작한다.
- malloc_consolidate (av) : fastbin에 흩어져 있는 모든 조각들을 병합하여 unsorted bin으로 옮긴다.
- 이 블록이 끝난 후 코드는 바깥 for ( ; ; ) 루프의 처음으로 돌아가서 Unsorted bin부터 탐색을 다시한다.
3. 시스템 메모리 할당
else
{
void *p = sysmalloc (nb, av);
if (p != NULL)
alloc_perturb (p, bytes);
return p;
}
- Top chunk도 부족하고, Fastbin을 정리해도 소용이 없는, 정말로 가용 메모리가 전혀 없는 상황이다.
- void *p = sysmalloc (nb, av) : 운영체제에 직접 메모리를 요청하는 sysmalloc 함수를 호출한다.
- 성공적으로 메모리를 받으면 그 주소를 실패하면 NULL을 반환한다.
'Pwnable > Heap' 카테고리의 다른 글
| Fastbin Consolidate (1) | 2026.01.14 |
|---|---|
| Fastbin Duplicate (0) | 2026.01.13 |
| Heap - glibc 2.23 (2) (1) | 2026.01.12 |
| Heap - glibc 2.23 (1) (0) | 2026.01.12 |
| Tcache dup (0) | 2025.05.20 |