heap의 개념-(3)
Boundary Tag
chunk가 할당 될 때는 해당 chunk의 크기 정보가 해당 chunk의 size에 저장이 된다.
chunk가 해제 될 때는 해당 chunk의 크기 정보가 다음 chunk의 prev_size에 저장이 된다.
이러한 정보로 우리는 인접한 앞/뒤 chunk의 주소 계산이 가능하다.
인접한 다음 chunk의 주소
chunk(A)를 기준으로 chunk_addr(A) + size(A) = chunk_addr(B) 가 된다. 이를 통해 다음 chunk의 주소를 알 수 있다.
인접한 앞의 chunk가 free된 경우의 freed chunk의 주소
chunk(B)를 기준으로 chunk(A)가 해제되었다면 chunk(B)의 prev_size가 초기화 된다.
그래서 chunk_addr(B) - prev_size(B) = chunk_addr(A) 를 통해 chunk(A)의 주소를 구할 수 있다.
binning
heap은 chunk를 재사용한다. 이때 free된 chunk를 크기 단위로 관리하는 것이 bin이다.
fast bin
- 최소 크기에서 8바이트(x86환경) 또는 16바이트(x64환경) 씩 정렬된다.
- 하나의 linked list에서는 size가 모두 같다.
- 10개(7개)의 bin으로 chunk를 single linked list 로 관리한다. FILO구조여서 fd만 사용한다.
- size는 16 ~ 64바이트(x86환경) 또는 32 ~ 128바이트(x64환경) 이다.
- 실제로는 32 ~ 176 바이트(x64환경)의 크기를 사용해서 10개이지만 7개만 사용한다. 그래서 128바이트까지이다.
- 메모리 단편화보다는 속도를 우선한다.
- 해제되어도 다음 chunk의 prev_inuse 값이 변경되지 않는다.
=> 인접한 chunk와 병합되지 않는다.
small bin
- 최소 크기에서 8바이트(x86환경) 또는 16바이트(x64환경) 씩 정렬된다.
- 하나의 linked list에서 size가 모두 같다.
- 62개의 bin으로 chunk를 double linked list로 관리한다. FIFO구조이다.
- size는 16 ~ 512바이트(x86환경) 또는 32바이트 ~ 1024바이트(x64환경) 이다.
- 해제가 되면 뒤 chunk의 prev_inuse bit 가 clear되고 prev_size가 초기화된다.
=> free할 때 인접한 freed chunk와 병합된다.(특수한 경우에 병합된다. unsorted bin 참고)
large bin
- 특정 범위의 size가 다른 chunk를 63개의 bin으로 double linked list로 관리한다. FIFO구조이다.
=> 하나의 linked list에서 서로 다른 size도 포함된다.
- size는 512바이트(x86) 또는 1024바이트(x64) 이상의 chunk가 들어간다.
- 한 linked list 내에서 size가 큰 chunk가 제일 앞으로 간다.
=> 한 linked list 내에서 다른 작은 크기를 가진 chunk를 가리키는 포인터로 fd_nextsize, bk_nextsize가 존재한다.
- 메모리 할당과 반환의 속도가 가장 느리다.
- 128KB 이상의 공간이 할당되는 경우 mmap() 시스템 콜을 거쳐 별도의 공간을 할당한 뒤에 chunk가 생성된다. 이렇게 생성될 경우 bin에 속하지 않고 IS_MMAPPED 플래그를 체크하며 munmap()으로 해제한다.
- 해제가 되면 뒤 chunk의 prev_inuse bit가 clear되고 prev_size가 초기화된다.
=> free할 때 인접한 freed chunk와 병합된다.
- fd(next_size)로 갈수록 chunk의 size는 작아지고 bk(next_size)로 갈수록 chunk의 size는 커진다.
- 같은 size를 가진 chunk 무리에서 가장 앞의(큰 chunk에 가까운)chunk만 fd_nextsize, bk_nextsize를 가진다.
-제일 큰 chunk의 bk_next_size는 제일 작은 chunk의 가장 앞 chunk를 가리킨다.(반대도 같음)
- 새로운 chunk가 들어갈 때 기본적으로 가장 앞으로 들어가지만 nextsize를 가진 chunk의 앞으로 가지는 않는다.
unsorted bin
- size 제한이 없는 double linked list 이다. FIFO 구조이다.
- 1개의 bin이 있다.
- unsorted bin에 들어가는 경우
1) free 했을 때 각 bin(small bin, large bin)으로 들어가기 전(fast bin 제외)
2) fast bin 들이 병합되어 합쳐질 때
=> fast bin은 일반적으로 병합이 되지 않지만 큰 크기의 chunk의 요청이 있으면 인접한 fast bin의 chunk를 한꺼번에 병합한다. 이러한 것을 malloc_consolidate라고 한다.
3) best fit으로 할당된 chunk의 남은 부분인 remainder
4) 병합된 free chunk
- unsorted bin에 나오는 경우
1) 사용자가 malloc을 호출하여 요청한 size와 동일한 chunk가 있을 때 해당 chunk가 allocated chunk로 바뀌면서 빠져나온다.
2) 사용자가 malloc을 호출했는데 요청한 chunk와 적합한 chunk가 없으면 unsorted bin에 있는 chunk를 각자 크기에 맞춰 bin으로 들어간다.
병합
free하려는 chunk의 앞, 뒤 chunk가 이미 해제되어 있을 때 병합이 발생한다.
해제하려는 chunk의 인접한 이전 chunk가 해제되어있는 경우에는 다음과 같은 순서에 따라 병합된다.
1) chunk(B)를 해제하려고 한다.
2) 이때 prev_inuse bit 가 설정되어있는지 보고 clear되어있으면 이전 chunk가 해제되어있다고 판단을 한다. 그리고 이전 chunk가 해제되어있으니 prev_size는 초기화되어있다.
3) chunk_addr(B)에서 prev_size를 빼면 chunk_addr(A)가 나온다.
4) 병합하려는 두 chunk의 주소를 알았으니 병합을 진행한다.
해제하려는 chunk의 인접한 이후 chunk가 해제되어있는 경우 다음과 같은 순서에 따라 병합된다.
1) chunk(A)를 해제하려고 한다.
2) chunk_addr(A)에 chunk_size(A)와 chunk_size(B)를 더한다. 그러면 chunk_addr(C)를 구할 수 있다.
3) chunk(C)의 prev_inuse bit가 clear되어있으면 이전 chunk(B)가 해제되어있다고 판단한다.
4) 두 chunk를 병합한다.
병합을 위해서는 binlist에 등록된 chunk를 제거해야 해서 freed chunk의 fd와 bk를 정리해줘야한다. 이를 unlink라고 한다.
<틀린 부분이 있다면 비난과 욕설을 해주세요>