(Heap 구조) bin구조

<bin>

bin은 free된 chunk들을 관리하는 데 사용된다.

 

청크 size를 기준으로 bin이 나눠진다.

- Fast bin (16~80bytes)

- Unsorted bin

- Small bin

- Large bin

 

<Fast bin>

size가 16~80bytes인 fast chunk들을 관리한다. fast chunk를 관리하는 bin을 fast bin이라고 한다.

모든 bin들 중 가운데, fast bin은 메모리 할당과 해제가 빠르다.

 

fast bin의 개수는 10개이고, 각 fast bin은 free된 fast chunk로 구성된 단일 연결리스트를 가진다.

단일 연결리스트는 리스트의 중간에서 chunk를 제거할 수 없기 때문에 chunk의 할당과 해제는 list의 앞쪽에서 발생한다.(LIFO : last_in_first_out : 나중에 들어온 것이 첫번째로 나간다.)

 

(일단 패스. 안 중요한듯..?->fast bin은 각 8bytes크기를 가지는 chunk의 binlist를 가진다.)

 

*fast chunk를 malloc할 경우

처음에는 fast bin의 최대 크기????와 fast bin index(fast bin의 공간)는 비어있기 때문에 사용자가 fast chunk를 요청하더라도 fast bin code가 아닌 small bin code가 이를 수행한다.

 

이후, 비어있지 않게 되면 fast bin index는 해당 binlist로 부터 계산된다.

사용자가 요청한fast chunk malloc에 fast binlist의 첫번째 fast chunk가 삭제되고 반환된다. (LIFO 구조)

 

*fast chunk를 free할 경우

free chunk는 binlist의 앞쪽에 추가된다. (LIFO 구조)

Fast bin list (단일 연결 구조)

<Unsorted bin> ....unsorted: 분류되지 않은

각각의 bin에서 추가가 아닌 해제되는 경우, unsorted bin에 추가된다.?????

 

small chunk 또는 large chunk들은 free가 됐다고 바로 해당 small bin, large bin 리스트에 들어가는 것이 아니라 unsorted bin에 들어간다.(fast bin은 예외)

그 이후 malloc 요청 시 동일한 크기의 영역을 다시 요청하는 경우 unsorted bin에 들어있는 청크를 바로 재사용할 수 있게 한다. (FIFO: first_in_first_out 방식으로 동작) 

 

malloc 요청으로 unsorted bin에서 검색된 청크들은 알맞은 사이즈인 경우 재사용을 하고, 

알맞은 사이즈가 아닌 경우에는 각자 자기의 bin(small bin or large bin)으로 돌!아!간!다!

즉, unsorted bin의 경우 단 한번의 재사용 기회만 주어진다.

 Unsorted bin, Small bin, Large bin

 

<Small bin>

size가 512bytes보다 작은 경우, small chunk라고 불린다. small chunk을 관리하는 bin을 small bin이라고 한다. 

small bin 은 메모리 할당 및 변환이 large bin보다 빠르다.(fast bin보다는 느리다.)

 

bin의 개수는 62개이다.

small bin은 이중 연결리스트이다.

이중 연결리스트가 사용되는 이유는 list의 중간에서 small chunk를 제거할 수 있기 때문이다.

chunk의 추가는 list의 앞에서 발생하고 삭제는 list의 뒤에서 발생한다. (FIFO 구조)

 

!!흥미로운사실!! binlist에서 해제된 2개의 chunk는 서로 인접해 있을 수 없다. 하나의 free chunk로 결합되기 때문이다.

 

*Small chunk가 malloc될 경우

초기에 모든 small bin은 비어있기 때문에 small chunk를 요청해도 small bin code대신 unsorted bin code를 수행한다.

또한, malloc을 처음 호출할 경우, small bin과 largebin의 bins(datastructures)는 malloc_state가 초기화되어 있기 때문에 찾을 수 있다.= bin이 비어있는 자기 자신을 가르키고 있다.

 

이후에 small bin이 비어있지 않게 되는 경우, 해당되는 binlist의 마지막 chunk가 제거된 후 사용자에게 반환된다.(FIFO구조)

 

*Small chunk가 free된 경우

현재 chunk를 해제하는 동안, 이전 또는 다음 chunk가 해제되었는지 확인한 후 그렇다면 해제된 chunk들을 결합한다.(앞에서 언급한 내용)

각각의 small binlist에서 chunk를 제거하고 unsorted bin의 시작부분에 새롭게 합병된 chunk를 추가한다.

 

 

<Large bin>

size가 512bytes보다 크거나 같은 경우, large chunk라고 하고, large chunk를 수용하는 bin을 large bin이라고 부른다.

large bin은 메모리 할당 및 반환이 small bin보다 느리다. 

 

bin의 개수는 63개이다.

이중 연결리스트 구조이다.

이중 연결리스트가 사용되는 이유는 list의 중간에서 large chunk를 제거할 수 있기 때문이다.

 

16개의 bin은 각 512byte 크기를 가지는 chunk의 binlist를 가집니다.

 

8개의 bin은 각 4,096byte 크기를 가지는 chunk의 binlist를 가집니다.

 

4개의 bin은 각 32,768byte 크기를 가지는 chunk의 binlist를 가집니다.

 

2개의 bin은 각 262,144byte 크기를 가지는 chunk의 binlist를 가집니다.

 

1개의 bin은 남은 크기를 가지는 chunk의 binlist를 가집니다.

 

!!집중!!small bin과 다르게 chunk의 크기가 같지 않더라도 같은 범위에 속하면 같은 리스트로 관리한다.즉, 4KB를 위한 bin이 있다면 이는 정확히 4096byte 크기의 chunk만을 포함하는것이 아니라 4000, 4080, 3999 등의 크기를 가지는 chunk들도 포함한다.

 

각 chunk들은 할당의 효율성을 위해 내림차순으로 정렬되어 저장됩니다. 가장 큰 chunk는 binlist의 가장 앞쪽에 저장되고, 가장 작은 chunk는 blinlist의 가장 뒷쪽에 저장된다.이때 fd_nextsize와 bk_nextsize 필드가 이용되며 이들은 현재 bin 내에서 크기가 다른 첫 번째 chunk에 대한 포인터를 저장한다.

 

또, 해제된 2개의 chunk는 서로 인접해 있을 수 없으며, 하나의 free chunk로 결합됩니다.

 

 

*Large chunk가 malloc된 경우초기의 모든 large bin은 비어있기 때문에 사용자가 large chunk를 요청했더라도, large bin code 대신 next largest bin code가 이를 수행한다.

또한, malloc을 처음 호출할 경우, small bin과 largebin의 bins(datastructures)는 malloc_state가 초기화되어 있기 때문에 찾을 수 있다.= bin이 비어있는 자기 자신을 가르키고 있다.

 

+이후 large bin이 비어있지 않을 때, 사용자가 요청한 크기가 binlist의 맨 첫번째 chunk(largest chunk)보다 작다면, binlist를 뒷쪽 끝부터 앞쪽 끝까지 확인하여, 사용자가 요청한 크기에 가깝거나 같은 크기의 chunk를 찾는다.찾게 되면, 해당 chunk는 2개의 chunk로 분리되고, 사용자가 요청한 크기의 chunk는 사용자에게 반환되고 나머지 크기는 unsorted bin에 추가된다.

 

+또 다른 경우로, 사용자가 요청한 크기가 binlist의 맨 첫번째 chunk보다 크면, 비어있지 않은 next  largest bin을 사용하여 사용자의 요청에 응답한다.??????next largest bin

next largest bin code는 비어있지 않은 next largest bin을 찾기 위해 binmaps를 스캔해서 해당하는 bin을 찾은 경우, 해당 binlist에서 적합한 chunk가 검색되고, 적합한 chunk를 분리하여 사용자에게 반환된다.

만약, 찾지 못한 경우 top chunk를 사용해 사용자의 요청에 응답한다.

 

*Large chunk가 free될 경우

(small bin 과정과 유사)

현재 chunk를 해제하는 동안, 이전 또는 다음 chunk가 해제되었는지 확인한 후 그렇다면 해제된 chunk들을 결합한다.

각각의 large binlist에서 chunk를 제거하고 unsorted bin의 시작부분에 새롭게 합병된 chunk를 추가한다.