Heap 구조
급하게 힙을 공부해야 할 일이 생겼다.
왠지 힙이 어려워서.. 그냥 눈으로 읽으면서 공부하기엔 무리가 있더라
직접 문서화하면서 공부해보기로.
철저히 필자 편하자고 하는 문서화라 서술이 좀 별로일거임.
a = malloc(8);
b = malloc(8);
c = malloc(8);
스택이랑 반대로 최근에 쌓인게 더 높은 주소를 가진다. (그림 상에서 밑으로 쌓이는 것임)
1. malloc된 chunk 구조
- prev_size : 이전 chunk의 크기
- size : 현재 chunk의 크기
- P : 플래그
| Flag | 설명 |
| PREV_INUSE (P) | 1 - 이전 chunk가 사용중 0 - 이전 chunk가 free된 상태 |
| IS_MAPPED (M) | mmap() 시스템 콜을 통해 할당된 것인가? |
| NON_MAIN_ARENA (N) | 각 thread마다 다른 heap 영역을 사용하는 경우, 현재 chunk가 main heap에 속하는가? |
- data : 값이 저장되는 영역
2. free된 chunk 구조
data 부분만 바뀌었다.
- fd (forward pointer) : 아직 사용되지 않은 다음 chunk의 주소
- bk (backward pointer) : 아직 사용되지 않은 이전 chunk의 주소
이 그림에서 주목할 점은 다음 chunk의 prev_size 필드가 현재 chunk의 데이터 영역으로 사용된다는 것
무슨 말인가 하면
- prev_size는 사실 이전 chunk에서 free()할 때 본인의 size를 중복해서 저장하는 것임
- 현재 chunk 시점에서 볼 때 이전 chunk의 size이므로, 현재의 데이터만을 다룬 actual chunk를 따로 표현하는 것
- 현재 chunk의 prev_size는 이전 chunk의 free() 시 설정됨
* 여기서 말하는 현재 chunk는 actual 말고 malloc chunk를 말하는 것임.
free() 시에는 다음 chunk의 PREV_INUSE 플래그를 지워야함
아 이 부분 왤케 힘들지
3. bins
bin은 freelist data structures이다. free chunk들을 수용하는데 사용
청크의 크기를 기준으로 사용하는 bin이 달라짐
- fast bin
- small bin
- large bin
- unsorted bin
사용하는 Data structures
- fastbinsY : fast bin을 수용하는 배열
- bins : unsorted, small, large bin 수용
Fast bin
청크의 크기가 아래에 해당하는 경우, fast chunk라 부름
32비트 기준 : 16~88 byte
64비트 기준 : 32~128 byte
fast bin : fast chunk를 수용한 bin. 총 10개 존재. 각 8byte
모든 bin들 중 fast bin은 메모리 할당과 해제가 가장 빠름. 이름값 하네
- 스택처럼 LIFO 방식 사용
- 속도 향상을 위해 싱글 링크드리스트로 구현되어 있음
-> 그로 인해 bk 값을 사용하지 않음
- 인접한 청크가 free() 되어도 병합 x
- 내부의 chunk는 동일한 크기이며, 정렬이 필요 x
만약 malloc 크기와 같은 크기의 패스트빈이 free() 상태로 존재한다면?
-> 동적생성 x. free()된 패스트빈을 재활용함 -> 여기서 fd 오버라이팅 취약점 발생!
Small bin
- 패스트빈과 다르게 FIFO 방식 사용
- 512 바이트 크기 까지의 62개의 bin 사용 (fast bin이 small bin에 포함됨)
- bin list는 각 8 byte의 크기를 가짐
- fd와 bk 모두 활용한 이중 연결 리스트 형태로 관리
- 인접한 두 청크가 free() 상태라면 병합 진행. fast bin과 다른 부분임
- small bin 내부의 chunk는 동일한 크기이며, 정렬이 필요 x
Large bin
- 512 바이트보다 큰 청크 관리
- 63개의 bin 사용
- 이중 연결리스트
- 사이즈가 다른 청크들도 같은 범위에 속하면 같은 리스트로 관리 함
- 대신 빈 안에서 크기별로 내림차순으로 정렬 진행
- 인접한 두 청크가 free() 상태라면 병합 진행.
사용자가 요청한 크기가 binlist의 맨 첫번째 청크(가장 큰 청크)보다 크다면?
-> 비어있지 않은 next largest bin을 사용하여 응답
next largest bin : binmaps 스캔 후 해당하는 bin을 찾은 경우, 해당 binlist에서 적합한 청크가 검색 되고 적합한 청크를 준리하여 사용자에게 반환함.
-> 찾지 못한 경우 top chunk를 이용해 반환
Unsorted bin
일종의 Cache 역할.
- 한 개의 bin만 존재
- 크기에 상관없이 FIFO 방식으로 관리
small, large 청크는 free가 되었다고 바로 해당 bin 리스트에 들어가지 않음.
unsorted bin에 들어가게 되고, 메모리 할당 시에 unsorted bin을 제일 먼저 확인하여 같은 크기의 chunk가 있다면 해당 chunk를 재사용하게 함
그리고 이 과정에서 한번 검색을 거쳤음에도 사용되지 않은 청크들은 각자 자신이 속해야할 bin list로 들어가게 됨
Top Chunk
top chunk : arena의 가장 꼭대기에 있는 청크
어떤 bin에도 속하지 않음.
bin들 중 하나에 해제된 청크가 없는 경우, 사용자의 요청에 응답하기 위해 사용
사용자가 요청한 크기가 Top chunk보다 작을 때?
- User Chunk(사용자가 요청한 크기) + Remainder chunk(나머지 크기)
- 여기서 remainder chunk가 새로운 top chunk가 됨
만약 요청한 크기가 top chunk보다 크다면?
- sbrk 또는 mmap syscall 을 사용해 top chunk 확장
참고