힙(Heap) 구조 - Linux

[구조] - (line당 4bytes단위)

(Header)

━━━━━━━━━━━━━━━━━━━━━━━━━ (malloc chunk)

Prev_Size

━━━━━━━━━━━━━━━━━━━━ (actual chunk)

Size | N | M | P |   -- 힙 크기가 8bytes 단위이므로, 뒤의 3bit는 "Flags"로 사용된다.

-----------------------

(Data)

FD

BK

FD_nextsize  ┐

BK_nextsize  ┘ LargeBin에서만 사용됨. 크기가 다른 첫번째 Chunk를 가리킴.

[Chunk data....]

[Chunk data....]

[Chunk data....]

━━━━━━━━━━━━━━━━━━━━━━━━━

Prev_Size   -- 인접한 다음 Chunk의 Prev_Size도 현재 Chunk영역으로 사용된다.

free() 시에 현재 Chunk의 Size를 중복으로 저장한다. (Flags 제외)

━━━━━━━━━━━━━━━━━━━━

[설명]

Prev_Size : 물리적으로(주소) 인접한 이전 Chunk의 Size를 나타낸다.

사실 Prev_Size는 이전 Chunk에서 Free() 시 본인의 Size를 중복해서 저장하는 것이다.

따라서 현재 Chunk 시점에서 보면 이전 Chunk의 Size인 것이다. actual_chunk라고 표시한 이유이다.

현재 Chunk의 Prev_Size는 이전 Chunk의 Free() 시 설정된다.

현재 Chunk 시작주소에서 Prev_Size만큼을 빼면 이전 Chunk의 header 주소를 구할 수 있다.

Size : 현재 Chunk의 Size이다.

현재 Chunk의 시작주소에서 Size(현재Chunk 크기)를 더해주면 다음 Chunk의 시작주소를 얻을 수 있다.

주소는 8bytes단위로 할당되므로, 맨 뒤의 3bit는 Flags로 활용된다.

(Flags)

N (NON_MAIN_ARENA) : 멀티 스레드 각각에서 힙을 할당할 경우 해당 힙이 main arena에 속한 것인지 표시한다.

M (IS_MMAPPED) : 해당 필드가 mmap() 시스템 콜로 할당된 것인지 표시한다.

P (PREV_INUSE) : 이전 Chunk가 사용중인지 여부를 표시한다. 이전 Chunk의 Free() 시 0으로 설정된다.

-----------------------(이후에 설명하는 것들은 Freed Chunk에서 사용)----------------

Free된  Chunk는 "Bin"에서 관리되며, 각각의 Bins들은 동일한 크기별로 관리된다.

해당 크기의 Bin 내에서 FD와 BK를 통한 이중연결리스트로 관리된다.

[Bins 설명]

SmallBin - 16, 24, 32, 48, ..... , 504btyes까지 8bytes단위의 총 62개의 Bins

SmallBin에서 작은 크기의 Chunk는 SingleLinkedList로 구성된 FastBin에서 관리된다.

FastBin - FD를 사용하지 않고,LIFO 방식의 Single Linked List로 관리되며 빠르다. alloc(), free() 시 가장 먼저 확인하는 Bin이며 병합이 일어나지 않는 이상 계속 남아있을 수 있다.

크기 : metadata포함  32bit기준 0x10~0x40(헤더0x08)

 64bit기준 0x20~0x80(헤더0x10)

LargeBin - 504bytes 이상  ----> Size가 같지 않아도 됨. (Sorted)

UnsortedBin - 일종의 Cache 역할. Free()시 바로 Bins에 들어가지 않고, 한번의 재사용 기회를 가짐.

---------------------------------------------------------------------------------------------

FD : 다음 Chunk의 주소 Forward

BK : 이전 Chunk의 주소 Backward

FD와 BK는 Free()되기 전까지는 그냥 Heap Data영역으로 사용되다가, Free() 시에 설정된다.

Bins들은 사실 FD와 BK로 이어지는 Double Linked List일 뿐이다.

Ex) - [SmallBin]

16 <->16 <-> 16 <-> 16

24

32 <-> 32 <->32

48 <-> 48

이런식으로 Bins들은 같은 크기별로 Double Linked List로 구성된다.

FD_Nextsize

BK_Nextsize

앞에서 예시를 들은 SmallBin과 다르게 LargeBin은 504bytes를 넘는 Chunk들을 모두 담는다. (Sorted된 상태)

FD_Nextsize와 BK_Nextsize는 LargeBin 범위의 Chunk 할당 요청 시, 현재 보고있는 크기가 요청에 부합하지 않을 경우 재빠르게 다음, 이전 크기의 청크로 이동하며 크기를 비교하 할당하기 위해 사용된다. 다음 크기의 가장 첫번째 Chunk의 주소를 담는다.