![[Heap] ptmalloc2](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2Fb4WX5o%2FbtqIxZql1PS%2FjTgI1K0UyYSGMFQRd1La1k%2Fimg.png)
Memory Allocator
dlmalloc, ptmalloc2, jemalloc, tcmalloc, libumem 등의 메모리 할당자
대부분의 운영체제에서 동적할당 시, 힙 페이지 생성
ptmalloc2
리눅스 GLIBC (GNU C Library)에서 사용하는 메모리 할당자
서로 다른 스레드가 서로 간섭X ,서로 다른 메모리 영역에 접근
dlmalloc 코드를 기반으로 멀티 스레드에서 사용되도록 확장; 한 번에 두개 이상의 메모리 영역을 활성화 해 멀티 스레드 효율적으로 처리복수의 스레드가 동시에 malloc을 호출: 각 스레드는 별도의 heap segment 생성 + 해당 heap을 유지 보수하는 데이터 구조 분리해 메모리에 할당
| $ wget https://ftp.gnu.org/gnu/glibc/glibc-2.23.tar.xz $ tar -xvf glibc-2.23.tar.xz |
△ ptmalloc2 메모리 할당자 구현을 위한 GLIBC 코드를 받아야 한다
Chunk
동적으로 할당된 heap 메모리malloc_chunk 구조체를 사용In-use chunk, Free chunk, Top chunk, Last Reminder chunk 로 분류각 chunk에는 크기, 인접한 chunk의 위치에 대한 메타 데이터(→ 해당 chunk가 현재 사용여부 확인 가능 + 이전 청크가 사용중인지도 확인 가능) 포함
malloc_chunk 구조체
struct malloc_chunk;
typedef struct malloc_chunk* mchunkptr;
struct malloc_chunk {
INTERNAL_SIZE_T prev_size; /* Size of previous chunk (if free). */
INTERNAL_SIZE_T size; /* Size in bytes, including overhead. */
struct malloc_chunk* fd; /* double links -- used only if free. */
struct malloc_chunk* bk;
/* Only used for large blocks: pointer to next larger size. */
struct malloc_chunk* fd_nextsize; /* double links -- used only if free. */
struct malloc_chunk* bk_nextsize;
};
구조체 멤버들
| prev_size | 이전 heap chunk가 free chunk가 되면 해제된 heap chunk의 크기를 저장 해제 되기 전에는 이전 힙 청크의 데이터 영역으로 사용 |
| size | In-use chunk의 크기 |
| flags (3bit) | 필드의 맨 끝 3bit - PREV_INUSE (P): 이전 heap chunk가 해제된 경우 설정 1 = 이전 청크 해제 X, 0 = 이전 청크 해제 O - IS_MMAPPED (M): 현재 청크가 mmap 시스템 콜을 사용해 할당된 경우 설정 - NON_MAIN_ARENA (N): 현재 청크가 main_arena에서 관리하지 않을 경우 설정 |
| FD (Forward pointer) | 다음 free chunk의 포인터 |
| BK (Backward pointer) | 이전 free chunk의 포인터 |
| fd_nextsize | large bin에서 사용하는 포인터, 현재 heap chunk의 크기보다 작은 heap chunk의 주소를 가리킴 |
| bk_nextsize | large bin에서 사용하는 포인터, 현재 heap chunk의 크기보다 큰 heap chunk의 주소를 가리킴 |
* fd, bk, fd_nextsize, bk_nextsize 는 현재 chunk가 free chunk일 경우에만 사용
* chunk의 크기 = MALLOC_ALIGNMENT(2*sizeof(size_t))의 배수 ; 32bit의 경우 size_t = 4byte >> chunk의 크기는 8의 배수
64bit의 경우 size_t = 8byte >> chunk의 크기는 16의 배수
In-use chunk
할당자로부터 메모리를 할당받아 사용중인 메모리 청크
메모리에서 in-use chunk 확인해보기
//In-use.c
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
void main(){
char *heap1 = malloc(136);
char *heap2 = malloc(80);
free(heap1);
char *heap3 = malloc(136);
read(STDIN_FILENO,heap3,136); //heap3가 가리키는 메모리에 데이터 입력
}
△ malloc 함수 호출 전
시스템은 heap 공간을 필요한 경우에만 process에 mapping하기 때문에 기본적으로 mapping 되어 있지 않다.
△ 첫 번째 malloc 함수 호출 후 (ni)
process에 heap 공간이 mapping되어 있다.
첫 번째 heap(heap1)의 포인터 = 0x602010
size (0x602008): 0x91 저장
chunk의 크기: MALLOC_ALIGNMENT(2*sizeof(size_t))으로 현재 64bit기 때문에 16의 배수가 되어야한다.
136(0x88)은 16의 배수가 아니기 때문에 136에 가장 가까운 16의 배수인 144의 크기로 chunk를 할당
+
PREV_INUSE [P] (0x1) 플래그 값: 현재 chunk가 프로세스에 매핑된 heap 공간의 최상위에 존재하기 때문에 해당 chunk 앞에 새로운 chunk가 할당된다.
▶ 145(0x91)
bk(0x602098): 할당이 가능한 메모리의 크기 저장(=0x91)
△ 두 번째 malloc 함수 호출 후 ( c )
두 번째 heap(heap2) pointer = 0x6020a0
chunk의 크기(size)(0x602098) = 0x61(97)애플리케이션이 요청한 크기 0x50 (80) + 청크를 관리하기 위해 필요한 메타데이터(fd, bk)를 저장을 위한 0x10 (16) + 해당 청크 앞에 사용중인 청크가 있기 때문에 PREV_INUSE [P] 0x1
△ free 함수 호출 후 ( c )
첫 번째 chunk(heap1) (0x602010) 해제한다.
0x602010 ~ 0x602018 메모리: fd, bk 값 저장
두 번째 chunk의 prev_size: 해제된 chunk의 크기(0x90) 저장
size: PREV_INUSE [P] (0x1) 플래그 값이 빠진 값 0x60 저장
△ 세 번째 malloc 함수 호출 후 ( c )
세 번째 heap(heap3)의 포인터 = 0x602010 = 처음 할당된 포인터
malloc()은 메모리 효율성을 위해 free chunk를 관리한다. 메모리 할당을 요청 받았을 때 free chunk를 먼저 사용한다.
다시 할당받은 chunk(현재 heap3 위치)는 이전에 저장된 데이터가 초기화되지 않고 그대로 존재한다.
두 번째 chunk의 size: 0x60 → 0x61 (두 번째 chunk의 앞에 chunk가 할당되어 사용중이기 때문에 PREV_INUSE 플래그 값 추가)
△ read 함수를 통해 heap3에 데이터 입력
값을 입력 → 이전에 저장되어 있던 값을 덮어쓴다.
Free chunk
할당자에게 반환된 chunk
* chunk의 크기에 따라 fd, bk, fd_nextsize, bk_nextsize의 값이 chunk 내에 저장된다.
* chunk의 크기가 최소의 크기인 경우: fd_nextsize, bk_nextsize의 값을 저장할 수 없다. → free chunk의 크기가 커지지 않는다.
== fd_nextsize, bk_nextsize는 큰 블록에서만 사용된다.
메모리에서 free chunk로 인한 메모리의 변화 확인하기
#include <stdio.h>
#include <stdlib.h>
void main(){
char *heap1 = malloc(128);
char *tmp2 = malloc(8);
char *heap2 = malloc(128);
char *tmp3 = malloc(8);
char *heap3 = malloc(128);
char *tmp1 = malloc(8);
free(heap1);
free(heap2);
free(heap3);
}
△ 6번의 malloc함수 호출 후
chunk의 크기가 128byte인 메모리 3개 할당 + chunk의 크기가 8byte인 메모리 3개 할당
△ 첫 번째 free 함수 호출 후 ( c )
heap1 (0x602010) 해제
tmp2의 prev_size = 0x90 (이전 chunk heap1의 크기)
tmp2의 size = 0x20 = PREV_INUSE (0x1) 플래그 값을 뺀 값
△ 두 번째 free 함수 호출 후 ( c )
heap2 (0x6020c0) 해제 → fd, bk 값 저장
fd (0x6020c0): tmp3 chunk 앞에 있는 free chunk의 mchunkptr(0x602000)저장heap1의 bk (0x602018): heap2의 mchunkptr(0x6020b0) 저장
△ 세 번째 free 함수 호출 ( c )
heap3 (0x602170) 해제
fd (0x602170): tmp1 chunk 앞에 있는 free chunk의 mchunkptr(0x6020b0) 저장heap2의 bk (0x6020c8) : heap3의 mchunkptr(0x602160) 저장
Top Chunk
heap memory의 마지막에 위치한 chunk
* top chunk의 마지막 = heap memory 영역의 끝* 메모리 할당 요청이 들어왔을 때 free chunk가 없는 경우 top chunk를 쪼개어 사용한다.* bin에 포함되지 않는다.
Last Remainder chunk
작은 사이즈의 할당 요청이 들어왔을 때, Free chunk가 쪼개지고 남은 chunk* 연속된 작은 사이즈의 할당 요청이 들어왔을 때 비슷한 주소에 heap chunk가 할당되는 할당의 지역성을 유지하기 위해 사용된다.
Bin
free chunk는 bin이라는 freelist 구조체를 통해 관리
* freelist: 동적으로 메모리를 할당하고 해제할 때 메모리 관리의 효율을 높이기 위해 할당되지 않은 영역을 관리하는 연결 리스트메모리 해제: 해제하려는 영역을 free list에 추가 → 할당 요청: freelist에 추가된 영역을 리스트에서 제거하고 해당 영역 사용
크기와 히스토리에 따라 다양한 bin에 저장
Fast bin
작은 크기의 heap chunk를 할당하고 해제할 때 사용하는 bin
chunk의 크기: 16~64 byte (32bit), 32~128byte (64bit)
Symbol param # default allowed param values
M_MXFAST 1 64 0-80 (0 disables fastbins)
M_TRIM_THRESHOLD -1 128*1024 any (-1U disables trimming)
M_TOP_PAD -2 0 any
M_MMAP_THRESHOLD -3 128*1024 any (or 0 if no MMAP support)
M_MMAP_MAX -4 65536 any (0 disables use of mmap)
////
/* M_MXFAST is a standard SVID/XPG tuning option, usually listed in malloc.h */
#ifndef M_MXFAST
#define M_MXFAST 1
#endif
#ifndef DEFAULT_MXFAST
#define DEFAULT_MXFAST (64 * SIZE_SZ / 4)
#endif
* "fastbin"에 포함되는 chunk의 범위: M_MXFAST(1) 매개변수 사용
* LIFO (Last-In Fast-Out) 방식 사용; 마지막으로 해제된 chunk가 가장 먼저 재할당
* 최대 10개의 bin 관리
* fastbin의 상한 값보다 작은 chunk들을 관리 - 64bit: 32, 48, 64, 80, 96, 112 byte의 chunk
* single-linked list로 구성; ptmalloc2의 bin 중 할당 및 해제 속도 가장 빠름
* 같은 bin에 포함된 chunk들끼리 서로 인접해도 하나의 chunk로 병합X
fastbin 크기를 가진 chunk의 해제 및 할당 과정
if ((unsigned long)(size) <= (unsigned long)(get_max_fast ()) //line1
#if TRIM_FASTBINS
/*
If TRIM_FASTBINS set, don't place chunks
bordering top into fastbins
*/
&& (chunk_at_offset(p, size) != av->top)
#endif
) {
if (__builtin_expect (chunk_at_offset (p, size)->size <= 2 * SIZE_SZ, 0)
|| __builtin_expect (chunksize (chunk_at_offset (p, size))
>= av->system_mem, 0))
{
/* We might not have a lock at this point and concurrent modifications
of system_mem might have let to a false positive. Redo the test
after getting the lock. */
if (have_lock
|| ({ assert (locked == 0);
mutex_lock(&av->mutex);
locked = 1;
chunk_at_offset (p, size)->size <= 2 * SIZE_SZ
|| chunksize (chunk_at_offset (p, size)) >= av->system_mem;
}))
{
errstr = "free(): invalid next size (fast)";
goto errout;
}
if (! have_lock)
{
(void)mutex_unlock(&av->mutex);
locked = 0;
}
}
free_perturb (chunk2mem(p), size - 2 * SIZE_SZ);
set_fastchunks(av);
unsigned int idx = fastbin_index(size);
fb = &fastbin (av, idx);
/* Atomically link P to its fastbin: P->FD = *FB; *FB = P; */
mchunkptr old = *fb, old2;
unsigned int old_idx = ~0u;
do //line41
{
/* 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))
{
errstr = "double free or corruption (fasttop)";
goto errout;
}
/* 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
deallocated. See use of OLD_IDX below for the actual check. */
if (have_lock && old != NULL)
old_idx = fastbin_index(chunksize(old));
p->fd = old2 = old;
}
while ((old = catomic_compare_and_exchange_val_rel (fb, p, old2)) != old2);
if (have_lock && old != NULL && __builtin_expect (old_idx != idx, 0))
{
errstr = "invalid fastbin entry (free)";
goto errout;
}
}△ free(fastbin) // free함수에서 fastbin chunk를 처리하는 코드
chunk가 해제될 때, 해당 chunk가 fastbin 크기의 범위에 있다면 [line1] 조건문 통과
→ [line 41] 현재 chunk의 크기에 해당하는 fastbin의 리스트 호출
→ 해당 fastbin freelist에 먼저 저장되어 있던 chunk 존재 시, [line 61] 저장되어 있던 chunk의 주소를 현재 해제된 chunk의 fd에 저장
= 해제된 chunk가 fastbin의 리스트에 추가
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); //return chunk ptr
alloc_perturb (p, bytes); //init
return p;
}
}△ malloc(fastbin) // fastbin freelist에 들어있는 chunk를 할당하는 과정
[line 4] 요청된 fastbin 크기와 부합하는 fastbin의 인덱스 검색
→ [line 12] 선택된 chunk의 fd가 가리키는 chunk를 fastbin의 첫 번째 리스트로 업데이트
→ [line 26] chunk를 반환
small bin
512byte(32bit)/1024byte(64bit) 미만의 사이즈의 chunk가 해제되었을 때 unsorted bin에 리스트가 추가된 후 저장되는 bin
smallbin 크기의 heap chunk 해제 → unsortedbin → smallbin에 할당
#define NBINS 128
#define NSMALLBINS 64
#define SMALLBIN_WIDTH MALLOC_ALIGNMENT
#define SMALLBIN_CORRECTION (MALLOC_ALIGNMENT > 2 * SIZE_SZ)
#define MIN_LARGE_SIZE ((NSMALLBINS - SMALLBIN_CORRECTION) * SMALLBIN_WIDTH)
#define in_smallbin_range(sz) \
((unsigned long) (sz) < (unsigned long) MIN_LARGE_SIZE)
//////
#define smallbin_index(sz) \
((SMALLBIN_WIDTH == 16 ? (((unsigned) (sz)) >> 4) : (((unsigned) (sz)) >> 3))\
+ SMALLBIN_CORRECTION)* small bin이 포함하는 chunk: MIN_LARGE_SIZE보다 작은 chunk들; 32bit-MIN_LARGE_SIZE=512 / 64bit-MIN_LARGE_SIZE=1024
* FIFO (First-In, First-Out) 방식 사용; 먼저 해제된 chunk가 먼저 재할당
* 64개의 bin들을 관리
* doubly-linked list로 구성; 같은 크기의 chunk들끼리 하나의 bin으로 연결
* small bin chunk들은 서로 인접하게 배치 될 수 없음 (인접해 있을 경우 하나의 chunk로 병합)
* small bin의 인덱스 확인: smallbin_index()함수
smallbin 크기의 chunk에 대한 할당 과정
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;
}
}
}[line1] 요청된 chunk의 크기가 smallbin크기에 부합한지 검사 → [line3] smallbin에 해당되는 배열 선정→ [line6] 반환될 chunk를 main_arena에서 얻어오면서 smallbin의 연결리스트가 비어있는지 확인비어있는 경우: malloc_consolidate 함수를 호출해 존재하는 fastbin과 병합비어있지 않은 경우: [line10] smallbin인 heap chunk를 재할당하는 코드 실행→ [line18] 인접한 chunk에 PREV_INUSE 플래그를 설정 / 반환될 chunk 뒤에 존재하는 chunk를 main_arena가 bk로 가리키게 함 / 해당 chunk의 fd는 main_arena를 가리키게 설정 ▷ 이중 연결 리스트 형성 & smallbin의 첫번째 리스트로 설정→ [line27] chunk를 반환하고 할당 과정 종료+) smallbin크기의 chunk가 해제되었을 때는 unsorted bin에서 확인 가능
Large bin
해제된 chunk의 크기가 512byte(32bit)/1024byte(64bit)이상
/*
Indexing
Bins for sizes < 512 bytes contain chunks of all the same size, spaced
8 bytes apart. Larger bins are approximately logarithmically spaced:
64 bins of size 8
32 bins of size 64
16 bins of size 512
8 bins of size 4096
4 bins of size 32768
2 bins of size 262144
1 bin of size what's left
There is actually a little bit of slop in the numbers in bin_index
for the sake of speed. This makes no difference elsewhere.
The bins top out around 1MB because we expect to service large
requests via mmap.
Bin 0 does not exist. Bin 1 is the unordered list; if that would be
a valid chunk size the small bins are bumped up one.
*/
///
#define largebin_index_32(sz) \
(((((unsigned long) (sz)) >> 6) <= 38) ? 56 + (((unsigned long) (sz)) >> 6) :\
((((unsigned long) (sz)) >> 9) <= 20) ? 91 + (((unsigned long) (sz)) >> 9) :\
((((unsigned long) (sz)) >> 12) <= 10) ? 110 + (((unsigned long) (sz)) >> 12) :\
((((unsigned long) (sz)) >> 15) <= 4) ? 119 + (((unsigned long) (sz)) >> 15) :\
((((unsigned long) (sz)) >> 18) <= 2) ? 124 + (((unsigned long) (sz)) >> 18) :\
126)
#define largebin_index_32_big(sz) \
(((((unsigned long) (sz)) >> 6) <= 45) ? 49 + (((unsigned long) (sz)) >> 6) :\
((((unsigned long) (sz)) >> 9) <= 20) ? 91 + (((unsigned long) (sz)) >> 9) :\
((((unsigned long) (sz)) >> 12) <= 10) ? 110 + (((unsigned long) (sz)) >> 12) :\
((((unsigned long) (sz)) >> 15) <= 4) ? 119 + (((unsigned long) (sz)) >> 15) :\
((((unsigned long) (sz)) >> 18) <= 2) ? 124 + (((unsigned long) (sz)) >> 18) :\
126)
// XXX It remains to be seen whether it is good to keep the widths of
// XXX the buckets the same or whether it should be scaled by a factor
// XXX of two as well.
#define largebin_index_64(sz) \
(((((unsigned long) (sz)) >> 6) <= 48) ? 48 + (((unsigned long) (sz)) >> 6) :\
((((unsigned long) (sz)) >> 9) <= 20) ? 91 + (((unsigned long) (sz)) >> 9) :\
((((unsigned long) (sz)) >> 12) <= 10) ? 110 + (((unsigned long) (sz)) >> 12) :\
((((unsigned long) (sz)) >> 15) <= 4) ? 119 + (((unsigned long) (sz)) >> 15) :\
((((unsigned long) (sz)) >> 18) <= 2) ? 124 + (((unsigned long) (sz)) >> 18) :\
126)
#define largebin_index(sz) \
(SIZE_SZ == 8 ? largebin_index_64 (sz) \
: MALLOC_ALIGNMENT == 16 ? largebin_index_32_big (sz) \
: largebin_index_32 (sz))
#define bin_index(sz) \
((in_smallbin_range (sz)) ? smallbin_index (sz) : largebin_index (sz))* large bin이 포함하는 chunk의 크기: MIN_LARGE_SIZE와 크거나 같은 chunk들; 32bit - 512이상, 64 - 1024 이상
* FIFO (First-In, First-Out) 방식 사용; 먼저 해제된 chunk가 먼저 재할당
* 63개의 bin들을 관리
* doubly-linked list로 구성; 하나의 bin에 다양한 크기의 chunk들을 크기별로 정렬해 보관 / fd_nextsize와 bk_nextsize를 사용해 서로 다른 크기의 chunk들을 리스트로 연결
* large bin chunk들은 서로 인접하게 배치 될 수 없음 (인접해 있을 경우 하나의 chunk로 병합)
* large bin의 인덱스 확인: largebin_index_32(), largebin_index_64() 함수를 이용
large bin에 들어 있는 chunk를 할당하는 과정
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;
}
}
[line1] large bin의 크기인지 검사→ [line6] large bin이 비어있는지 / 가장 큰 chunk가 요청된 크기보다 큰 지 검사
→ [line10] victim->bk_nextsize를 순회하며 요청된 크기에 부합하는 chunk 찾기
→ [line20] chunk의 반환 이후, 연결리스트를 유지하기 위해 unlik 매크로 사용
→ [line30] large bin chunk가 요청된 크기보다 큰 경우: remainder_size 검사해 MINSIzE보다 크면 unsorted bin과 연결리스트를 생성해 저장 last_remainder chunk의 크기 == large bin의 크기: fd_nextsize와 bk_nextsize를 NULL로 초기화
→ [line51] 반환될 chunk의 PREV_INUSE 플래그 설정 / last_remainder chunk도 PREV_INUSE 플래그를 설정해 현재 반환될 chunk가 할당된 상태임을 표시
Unsorted bin
small bin과 large bin 크기의 heap chunk가 해제되면 이후 재할당을 위해 사용되는 bin
* unsorted bin은 크기의 제한 X, 다양한 크기의 heap chunk를 저장 / fast bin에 해당하는 chunk는 배치되지 않음
* FIFO (First-In, First-Out) 방식 사용; 먼저 해제된 chunk가 먼저 재할당
* 1개의 bin
* doubly-linked list로 구성; 해제된 chunk를 재사용하기 위해 해제된 chunk의 크기보다 자거나 동일한 크기의 chukn가 할당되어야 한ㅁ
* large bin chunk들은 서로 인접하게 배치 될 수 없음 (인접해 있을 경우 하나의 chunk로 병합
//unsorted bin1
/* Take now instead of binning if exact fit */
INTERNAL_SIZE_T nb; /* normalized request size */
checked_request2size (bytes, nb);
size = chunksize (victim);
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;
}
//unsorted bin2
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;
}
//unsorted bin3
if (in_smallbin_range (size))
{
victim_index = smallbin_index (size);
bck = bin_at (av, victim_index);
fwd = bck->fd;
}
victim->bk = bck;
victim->fd = fwd;
fwd->bk = victim;
bck->fd = victim;
//unsorted bin4
else
{
victim_index = largebin_index (size);
bck = bin_at (av, victim_index);
fwd = bck->fd;
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;
}
victim->bk = bck;
victim->fd = fwd;
fwd->bk = victim;
bck->fd = victim;unsorted bin1
unsorted bin의 size와 할당 요청이 들어온 크기 nb 비교 → 크기가 같다면 기존의 unsorted bin에 들어간 영역 재사용
unsorted bin2
할당 요청 받은 크기가 small bin에 해당 & 현재 unsorted bin에 저장된 chunk크기보다 작음 & unsorted bin의 chunk가 분할된 last_remainder chunk ▷ 요청 받은 chunk를 분할하여 남은 chunk를 unsorted bin과 last_remainder에 저장
unsorted bin3
smallbin의 크기가 unsorted bin에 남아있는 경우: smallbin 크기의 chunk는 smallbin으로 옮김크기를 검사하고 smallbin 중 옮겨진 chunk의 크기에 적합한 배열을 찾아 smallbin에 존재하는 chunk와 fd, bk 연결
unsorted bin4
largebin의 크기가 unsorted bin에 남아있는 경우: largebin 크기의 chunk를 largebin으로 옮김크기를 검사하고 largebin 중 옮겨진 chunk의 크기에 적합한 배열을 찾아 large bin에 존재하는 chunk와 fd_nextsize, bk_nextsize, fd, bk 연결
smallbin / large bin 크기의 chunk가 해제되고 unsorted bin에 삽입되는 과정
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);
fwd = bck->fd;
if (__glibc_unlikely (fwd->bk != bck))
{
errstr = "free(): corrupted unsorted chunks";
goto errout;
}
p->fd = fwd;
p->bk = bck;
if (!in_smallbin_range(size))
{
p->fd_nextsize = NULL;
p->bk_nextsize = NULL;
}
bck->fd = p;
fwd->bk = p;
set_head(p, size | PREV_INUSE);
set_foot(p, size);
check_free_chunk(av, p);clear_inuse_bit_at_offset 매크로: 인접한 chunk의 PREV_INUSE 플래그를 0으로 설정 → [line17-18] 새롭게 해제된 chunk를 리스트에 포함[line19] large bin 범위의 chunk가 해제되었을 경우 unsorted bin에서 사용하지 않는 메타데이터 fd_nextsize, bk_nextsize를 NULL로 초기화[line30] 현재 chunk가 해제되어있는지 검증
128KB 이상의 큰 메모리
mmap()에 새로운 메모리의 매핑을 요청한 후 해당 메모리에 chunk 할당* 해당 chunk들은 bin에 속하지 않음* IS_MMAPED 플래그를 설정
* munmap()을 호출해 해당 chunk들을 해제
Arena
ptmalloc2에서 각 스레드가 간섭하지 않고 서로 다른 메모리 영역에 액세스 할 수 있는 메모리 영역
main arena
malloc() 함수에서 main arena를 가리키는 정적변수가 있고 각 arena에는 추가 arena를 연결하는 포인터들이 있다.
각 arena는 하나 이상의 heap memory를 갖는다.
main arena: 프로그램 초기 heap 사용 (.bss 영역 등의 직후)추가 arena: mmap을 통해 heap에 메모리를 할당하고 이전 heap이 소모되면 더 많은 heap을 heap 목록에 추가
heap 메모리에서 할당된 chunk들을 관리한다.
arena에서 관리되는 chunk: 응용 프로그램에서 사용중이거나 사용이 가능한 chunk / 사용중인 chunk는 arena에서 추적 불가능free chunk를 크기와 히스토리에 따라 분류해 arena에 저장할당자는 arena에서 할당 요청을 충족하는 chunk를 신속하게 찾을 수 있음
main arena
brk 시스템 콜을 사용해 할당된 heap을 효율적으로 관리하기 위해 존재하는 malloc_state의 구조체malloc() 코드 내에 "main_arena"라는 매개변수를 선언해 사용 ▷ struct malloc_state 구조체를 사용
/* There are several instances of this struct ("arenas") in this
malloc. If you are adapting this malloc in a way that does NOT use
a static or mmapped malloc_state, you MUST explicitly zero-fill it
before using. This malloc relies on the property that malloc_state
is initialized to all zeroes (as is true of C statics). */
static struct malloc_state main_arena =
{
.mutex = _LIBC_LOCK_INITIALIZER,
.next = &main_arena,
.attached_threads = 1
};struct malloc_state
{
/* Serialize access. */
__libc_lock_define (, mutex);
/* Flags (formerly in max_fast). */
int flags;
/* Fastbins */
mfastbinptr fastbinsY[NFASTBINS];
/* Base of the topmost chunk -- not otherwise kept in a bin */
mchunkptr top;
/* The remainder from the most recent split of a small request */
mchunkptr last_remainder;
/* Normal bins packed as described above */
mchunkptr bins[NBINS * 2 - 2];
/* Bitmap of bins */
unsigned int binmap[BINMAPSIZE];
/* Linked list */
struct malloc_state *next;
/* Linked list for free arenas. Access to this field is serialized
by free_list_lock in arena.c. */
struct malloc_state *next_free;
/* Number of threads attached to this arena. 0 if the arena is on
the free list. Access to this field is serialized by
free_list_lock in arena.c. */
INTERNAL_SIZE_T attached_threads;
/* Memory allocated from the system in this arena. */
INTERNAL_SIZE_T system_mem;
INTERNAL_SIZE_T max_system_mem;
};△ malloc_state 구조체mutex: 해당 arena에 대한 액세스를 제어; 여러 스레드 간 arena 사용 충돌을 방지한다. fast bin에 대한 액세스 등의 일부 작업은 arena를 잠글 필요가 없지만 이 외의 다른 모든 작업을 위해서는 스레드가 arena를 잠궈야한다.
#define FASTCHUNKS_BIT (1U)
#define have_fastchunks(M) (((M)->flags & FASTCHUNKS_BIT) == 0)
#define clear_fastchunks(M) catomic_or (&(M)->flags, FASTCHUNKS_BIT)
#define set_fastchunks(M) catomic_and (&(M)->flags, ~FASTCHUNKS_BIT)
/*
NONCONTIGUOUS_BIT indicates that MORECORE does not return contiguous
regions. Otherwise, contiguity is exploited in merging together,
when possible, results from consecutive MORECORE calls.
The initial value comes from MORECORE_CONTIGUOUS, but is
changed dynamically if mmap is ever used as an sbrk substitute.
*/
#define NONCONTIGUOUS_BIT (2U)
#define contiguous(M) (((M)->flags & NONCONTIGUOUS_BIT) == 0)
#define noncontiguous(M) (((M)->flags & NONCONTIGUOUS_BIT) != 0)
#define set_noncontiguous(M) ((M)->flags |= NONCONTIGUOUS_BIT)
#define set_contiguous(M) ((M)->flags &= ~NONCONTIGUOUS_BIT)△ main_arena에서 사용하는 flags2개의 bit로 정보들의 유무 표현
첫 번째 bit: 해당 arena가 fastbin(fastchunk)를 가지고 있는지 -- fastbin이 arena에 있으면 0, 없으면 1
두 번째 bit: 해당 arena가 인접한지 -- 해당 arena가 인접해 있다면 1, 인접하지 않았다면 0non-main arena는 하위 heap으로 구성되고, 항상 NONCONTIGUOUS_BIT가 설정
if (av == NULL
|| ((unsigned long) (nb) >= (unsigned long) (mp_.mmap_threshold)
&& (mp_.n_mmaps < mp_.n_mmaps_max)))
{
char *mm; /* return value from mmap call*/
try_mmap:
/*
Round up size to nearest page. For mmapped chunks, the overhead
is one SIZE_SZ unit larger than for normal chunks, because there
is no following chunk whose prev_size field could be used.
See the front_misalign handling below, for glibc there is no
need for further alignments unless we have have high alignment.
*/
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;
/* Don't try if size wraps around 0 */
if ((unsigned long) (size) > (unsigned long) (nb))
{
mm = (char *) (MMAP (0, size, PROT_READ | PROT_WRITE, 0));△ Top Chunk의 배치
Top chunk는 arena의 최상위 영역에 있는 chunk로, bin에 포함되지 않는다.
* arena의 최상위 영역의 chunk로, bin에 포함되지 않는다
* PREV_INUSE 플래그 설정
* 요청한 heap을 할당할 수 있는 충분한 chunk가 bin에 없는 경우에 사용
* Top chunk의 크기가 사용자가 요청한 크기보다 큰 경우 2개로 분리되어 사용자가 요청한 크기의 chunk + remainder chunk
→ remainder chunk는 새로운 top chunk가 된다.
Top chunk의 크기보다 큰 사이즈의 할당 요청이 들어오면 mmap 시스템 콜을 사용해 새로운 페이지를 할당한다. → 이렇게 할당된 heap은 main arena에서 관리하지 않는다.
/*
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));
LIBC_PROBE (memory_sbrk_more, 2, brk, size);
}△ sbrk() 호출
메모리를 할당하기에 arena의 공간이 부족할 경우: sbrk()를 호출해 메모리 공간을 증가시킨다.
* malloc.c 코드에서는 MORECORE라는 매크로를 이용해 sbrk() 함수를 호출한다.
할당과 해제를 반복한 후 main_arena 확인
#include <stdio.h>
#include <malloc.h>
int main()
{
char *ptr = malloc(0x10);
free(ptr);
char *ptr2 = malloc(0x20);
free(ptr2);
}
△ 다른 크기의 heap을 두 번 할당하고 해제한 모습
fastbinsY: fastbin 크기로 할당되고 해제된 heap을 수용하는 배열; 해제된 두 개의 heap 주소가 쓰여져 있다.
해제된 heap과 동일한 크기를 할당하게 되면 fastbinsY를 참조해 할당하게 된다.
참고
www.lazenca.net/pages/viewpage.action?pageId=1147929
사진1,2 (azeria-labs.com/heap-exploitation-part-1-understanding-the-glibc-heap-implementation/)
in-use chunk, free chunk (r0hi7.github.io/BinExp/Lecture7/)
top chunk (d41jung0d.tistory.com/108)
'System > System Hacking' 카테고리의 다른 글
| [Heap] Double Free 취약점 (0) | 2020.09.17 |
|---|---|
| [Heap] Security Check (0) | 2020.09.13 |
| Return to csu (ft. Return-to-vuln, Just-In-Time Code Reuse) (0) | 2020.08.15 |
| Return to csu (ft. JIT ROP) (0) | 2020.08.14 |
| SROP x64 (0) | 2020.07.24 |