Chunk.

Chunk.

Chunk는 힙 영역에서 찾을 수 있으며, 4가지 타입이 있다.

1. Allocated chunk. (할당 된 청크)

2. Free chunk. (자유로운 청크)

3. Top chunk.  (상단 청크)

4. Last Remainder chunk. (마지막 남은 링크)

Allocated, Free chunk는 "malloc_chunk" 구조체를 이용해 필요한 정보를 저장한다.

1-1. Allocated chunk.

==> Allocated chunk 의 최소 크기는 32Bit = 16 byte. 64Bit = 32 byte.

위의 화면은 Allocated chunk Sample(64bit).

Allocated chunk는 정보를 포함한다.

prev_size ==> 이전 Chunk가 해제되면, 이 필드에 이전 Chunk의 크기가 저장된다.

                    이전 Chunk가 할당되면, 이 필드에 이전 Chunk의 사용자 데이터가 저장된다.

size ==> 이 필드는 Allocated chunk의 크기를 저장하며, 필드의 맨 끝 3bit는 flag 정보를 나타낸다.

             = prev_inuse [p] ==>  이전 청크가 할당되면 설정된다.

             = is_mmapped [m] ==> 현재 청크가 mmap를 통해 할당되면 설정된다.

             = non_main_arena [a] ==> 현재 청크가 thread arena에 위치되면 설정된다.

Allocated chunk는 구조를 확인 할 때.

해당 Chunk 앞에 해제된 Chunk가 없기 때문에 prev_size 영역은 비워져 있다.

size는 저장되어 있다.

--- Allocated chunk의 header 정보를 저장하는 공간. == 16byte.

--- 사용자가 요청한 heap 공간의 크기 == 8byte.

--  다음 chunk 정보를 저장할 공간 == 8byte

1-2 Fast chunk, Small chunk, Large chunk.

==> Allocated chunk는 chunk size+user data의 크기에 따라 구분된다.

2-1 Free chunk.

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를 저장된다.

Free chunk의 구조를 확인할 때.

Chunk size는 아래의 값을 더한 값이 저장된다.

Free chunk의 header 정보를 저장하는 공간 - 16byte.

해체된 heap 공간의 크기 - 128byte.

fd 영역에 해제된 heap1 영역의 주소가 저장되어 있다.

bk 영역에 해제된 heap2 영역의 주소가 저장되어 있다.

"prev_inuse" flag 설정 - 1byte.

3-1 Top chunk.

==> Arena의 가장 상위에 있는 chunk.

==> bin에 포함되지 X.

==> prev_inuse 플래그가 설정된다.

==> Top chunk의 크기가 사용자가 요청한 크기보다 큰 경우 top chunk는 2개로 분리된다. 

=======================>user chunk(사용자가 요청한 크기) ==========>remainder chunk(나머지 크기)

==> Remainder chunk는 새로운 Top chunk가 된다.

==> Top chunk의 크기가 사용자가 요청한 크기보다 작은 경우 system call을 사용하여 top chunk의 크기를 증가시킨다.

=======================>sbrk(main arena) ============>mmap(thread arena)

 

4-1 Last Remainder chunk.

==> Remainder는 요청에 의해 너무 작게 분할되어 만들어진다.

==> Last Remainder chunk는 연속된 작은 chunk의 malloc 요청은 결국 각각의 할당을 끝날 것이다.

==> 또한 지역 참조성을 증가시키는데 도움을 준다.

그럼 많은 chunk 중 적합한 정크는?

사용자가 작은 청크를 요청했는데, small bin과 unsorted bin으로 제공할 수 없는 경우, binmaps는 비어있지 않는 다음 largest bin을 찾기 위해 스캔된다. 비어있지 않는 다음 largest bin을 찾은 경우, 2개로 분리되어, user chunk는 사용자에게 반환되고 

remainder chunk는 unsorted bin에 추가된다. 이 추가로 새로운 last remainder chunk가 생겼다.

지역 참조성을 달성하려면...?

뒤늦게 사용자가 작은 청크를 요청했으나, last remainder chunk가 오로지 unsorted bin에만 있는 청크인 경우, last remainder chunk는 2개로 분리되어, user chunk는 사용자에게 반환되고 remainder chunk는 unsorted bin에 추가된다. 이 추가로 새로운 last remainder chunk가 생겼다. 이와 같은 후속 메모리 할당은 서로의 옆에 할당되는 것으로 끝난다.