[TechNote] malloc (Heap)

Heap

 

동적인 영역

 

1. Arena

 

메모리 관리 영역

프로세스에 할당된 heap 영역(non-mmapped)

 

1-1. main_arena

 

brk 시스템 콜 사용하여 할당된 힙을 효율적으로 관리하기 위해 malloc.c에서 “malloc_state” 구조체

top chunk 크기보다 큰 사이즈 할당 요청의 경우: mmap 시스텥ㅁ 콜 사용해서 새로운 페이지 할당 -> 이 힙은 main_arena에서 관리하지 않는다.

 

 

malloc을 하기 전에는 heap 메모리 공간이 없는데,

malloc을 하고 나면 heap 메모리 공간이 생기는 것을 gdb로 확인할 수 있다.

 

 

pwndbg> p main_arena

 

 

 

2. Chunk

 

할당 단위

 

-Allocated chunk

-Top chunk

 

2.1 Allocated chunk

 

1) Allocated 최소 크기

 

64bit : 0x20 byte

 

- header 0x10 byte가 한 행, 그 다음 data

한 행 당 0x10byte 크기 가지고, 각 0x8 byte 씩 크기

 

prev_size (0x8)	size (0x8)
user data

 

FD 포인터가 위치한 주소가 실제 데이터 영역의 시작 부분이고, 할당되었을 때는 FD 포인터로 사용하지 않는다.

0x18 바이트 malloc 하는 경우, 다음 헤더의 0x8 바이트까지 할당해준다.

 

* prev_size

 

- 이전 chunk가 해제된 경우 : 이 필드에 이전 chunk의 크기 저장 (해제된 이전 힙 청크의 크기)

- 이전 chunk가 할당된 경우 : 이 필드에 이전 chunk의 user data 저장 (해제되기 전에는 이전 힙 청크의 데이터 영역으로 사용)

 

=> 일반적으로 0

 

* size

 

- allocated chunk 크기 저장

* 필드 맨 끝 3bit는 flag 정보 나타냄

– PREV_INUSE (P) : 이전 청크가 할당된 경우 1 → 일반적으로 1, 이전 힙 청크가 해제된 경우 0

- IS_MMAPPED (M) : 현재 청크가 mmap 시스템 콜을 통해 할당된 경우

- NON_MAIN_ARENA (A) : 현재 청크가 thread arena에 위치된 경우 (현재 청크가 main_arena에서 관리하지 않을 경우)

top chunk 크기보다 큰 사이즈 청크 요청 시 mmap 시스템 콜로 할당하고, main_arena에서 관리하지 않으므로 NON_MAIN_ARENA 비트가 적용될 것이다.

 

pwngdb> heap

 

heapbase : 0x602000

 

pwndbg> x/10gx 0x602000 으로 확인해보면 헤더를 볼 수 있고, size 에 0x81이 저장되어 있음

 

(이전 chunk가 할당되어 있어서 0x80이 아닌 0x81임)

그리고 내려보면 0x80 바이트 공간이 마련되어 있고, 그 뒤에 0x20f81 이 있는데, 이건 할당하고 남은 부분, 즉 top chunk 부분이다.

 

pwndbg> vmmap

으로 확인해보면 커널에서 heap 영역으로 할당해준 부분이 0x602000 ~ 0x623000임을 알 수 있다.

 

 

2) chunk size 의 크기에 따른 Allocated chunk 분류

 

Fast chunk 0x20 ~ 0x80

Small chunk 0x90 ~ 0x200

Large chunk 0x200 ~

 

 

2.2 Free chunk

 

prev_size	size
fd	bk

 

* prev_size

 

- Free chunk 는 연속으로 붙어있을 수 없고, 각 청크를 해제하는 경우 하나의 free chunk로 결합된다.

- 항상 해제된 청크의 이전 청크를 할당하고 있어서 prev_size 는 이전 청크의 사용자 데이터를 저장한다.

 

* size

 

- Free chunk 의 크기 저장

- 필드 맨 끝 3bit는 flag

 

* fd (forward pointer)

 

- 동일한 Bin의 다음 Free chunk address 저장

 

* bk (Backward pointer)

 

- 동일한 Bin의 이전 Free chunk address 저장

 

* example code

 

 

prev_size : 0

size :

free chunk header 정보 저장 공간 0x10 byte + 해제된 heap 공간 크기 0x80 byte | “PREV_INUSE” flag 1 byte = 0x91

fd : 해제된 heap1 영역 주소 = 0x602000

bk : 해제된 heap2 영역의 주소 = 0x602160

 

2.3 Bin

 

“malloc_state” 구조체에서 Bin 정보 관리

- FastbinsY : fast bin 관리 (포인터)

- Bins : Unsorted bin, small bin, large bin 관리

 

* Fast bin

 

- chunk type : fast chunk

- free chunk 관리 : free chunk 가 서로 인접해 있어도 하나의 free chunk로 병합되지 않는다.

- single-linked list -> fast bin은 fd만 있고 bk는 없음

- 할당 및 해제 방식: LIFO(Last In First Out)

- “global_max_fast” : fast bin이 처리하는 메모리의 최대 크기 결정

- fastbin freelist에 저장되어 있는 청크가 존재하면, 그 청크의 주소를 현재 해제된 청크의 FD에 저장한다. 

해제된 청크가 fastbin의 single-linked list에 추가된다.

- freebin의 freelist에 있는 청크를 할당하는 방법: 현재 요청된 fastbin 크기와 부합하는 fastbin 인덱스를 찾는다. 

선택된 청크의 FD를 참조해서 FD가 가리키는 청크를 fastbin의 첫 번째 리스트로 업데이트해서 LIFO 구조 유지한다.

최종적으로 청크를 반환한다.

 

 

 

main_arena 정보를 출력해서 fastbinsY에 각 해제된 heap 영역 주소가 저장된 것을 확인할 수 있다.

fastbin이므로 unsorted bin에는 해제된 heap 영역 추가 안 됨

 

 

* Small bin

 

- chunk type : small chunk (512바이트 미만 크기)

- bin 개수: 62개

- free chunk 관리 : 2개의 free chunk는 서로 인접해 있을 수 없고 free chunk가 서로 인접해 있으면 하나의 free chunk로 병합된다.

- double-linked list

- FIFO 구조

- smallbin 크기 청크 할당 과정:

(1) 요청된 크기가 smallbin 크기에 부합하는지 검사 후 smallbin에 해당되는 배열 선정

(2) 반환될 청크를 main_arena에서 얻어오고 smallbin의 연결 리스트가 비었는지 확인 후, 비어있으면 malloc_consolidate 함수 호출해서 fastbin과 병합한다. 비어있지 않으면 smallbin인 힙 청크 재할당한다. 

 

* Large bin

 

- chunk type : large chunk (512바이트 이상 크기)

- bin 개수: 63개

-  free chunk 관리 : 2개의 free chunk는 서로 인접해 있을 수 없고 free chunk가 서로 인접해 있으면 하나의 free chunk로 병합된다.

- double linked list

- FIFO 구조

- fd_nextsize, bk_nextsize 사용 (다른 bin들과 다른 점) -> large bin 청크들을 리스트로 연결하기 위해 사용한다.

- large bin 청크 할당 과정

(1) large bin 청크 크기에 맞는지 검사

(2) large bin이 비어있는지, 가장 큰 청크가 요청된 크기보다 큰지 검사

- victim->bk_nextsize 순회하며 요청된 크기에 맞는 청크 찾는다.

(3) unlink 매크로 사용: 반환될 청크 제외 앞 뒤 청크들의 연결 리스트 유지하기 위해 사용

 

* Unsorted bin

 

- smallbin과 largebin 크기의 힙 청크가 해제되면 재할당 위해 사용되는 bin (unsorted bin 존재 목적)

-> clear_inuse_bit_at_offset 매크로 사용해서 다음 청크의 prev_inuse 비트를 0으로 만들고, 해제된 청크를 이중 연결 리스트에 포함시킨다.

- chunk type : small chunk, large chunk

- double linked list (이중 연결 리스트)

- FIFO 구조

 

 

- 1개의 bin 만 사용 → 할당과 해제의 처리속도 빠름

- 해제된 청크 재사용: 해제된 청크 크기보다 작거나 동일한 크기의 청크 할당되어야 한다.

 

- 할당 요청 들어온 크기가 smallbin 크기에 속하고 unsorted bin에 저장된 청크 크기보다 작고 last_remainder 청크일 경우(분할되고 남은 청크): 분할 후 남은 청크를 unsorted bin과 last_remainder에 저장한다.

smallbin 크기가 unsorted bin에 남아있는 경우: 해당 청크는 smallbin으로 옮겨진다. smallbin 중 크기가 적합한 배열을 찾아 smallbin에 존재하는 청크와 FD, BK를 연결한다.

- 다음 할당 요청까지 large bin 크기가 unsorted bin에 남아있는 경우: 해당 청크는 large bin에 옮겨지고, 크기 검사 후 large bin에서 크기 적합한 배열을 찾아 large bin에 있는 청크와 fd_nextsize, bk_nextsize 연결하고 FD, BK 연결한다. 

→ 검색된 chunk는 바로 재할당되거나 원래의 bin(small bin 또는 large bin)으로 돌아간다.

→ 해제한 chunk 재사용 위해서는 chunk 해제 후 바로 동일한 크기의 chunk 생성해야 함.

 

 

 

pwndbg> ni

 

 

free() 호출된 후 bins 1번째 인덱스 영역에 해제된 heap 영역 주소값 저장됨

 

 

2.4 Top chunk

 

- Arena의 가장 상위 영역에 있는 chunk

- PREV_INUSE 플래그 설정됨

- bin 에 포함되지 않음

 

* top chunk의 크기가 사용자가 요청한 크기보다 큰 경우 top chunk는 2개로 분리됨

 – user chunk(사용자가 요청한 크기)

– remainder chunk(나머지 크기) → 새로운 chunk가 됨

 

* top chunk 크기가 사용자가 요청한 크기보다 작은 경우 syscall 사용해서 top chunk 크기 증가시킴

- sbrk (main arena)

- mmap (thread arena)