3회차 회고록

목표

• HEAP 구조 정리 2

결과

지난 회차에 이어서 chunk의 종류를 정리해보았다.

top chunk

• wildness chunk

• 각 arena에서 최상위에 존재하는 chunk = heap 영역의 마지막에 위치

• 재사용 가능한 chunk가 없을 때 새롭게 할당되면 top chunk에서 분리해서 영역을 반환

• top chunk에 인접한 chunk가 free되면 병합

• 일반적으로 top chunk의 크기는 0x21000이고, Top chunk의 크기보다 큰 할당은 불가능

chunk 관리 알고리즘

• boundary tag

• Binning

boundary tag

• chunk의 크기 정보가 chunk의 앞 뒤에 저장

• size

  • chunk가 할당될 때 크기 정보가 해당 chunk의 size에 저장됨

• prev size

  • 이전 chunk가 해제될 때 크기 정보가 prev size에 저장됨

• In-use chunk와 free chunk가 있을 때 인접한 앞/뒤 chunk 주소 계산이 가능하다.

Binning

• 재사용 가능한 chunk를 크기 단위로 관리하기 위한 알고리즘

• Fast bin, small bin, large bin, unsorted bin + Tcache bin

Fasat bin

• size가 다른 10개의 chunk를 각각 single linked list로 관리(FILO)

• chunk의 size가 64byte 이하(32bit), 128byte 이하(64bit)

• 해제가 되어도 다음 chunk의 prev in use 값이 변경되지 않음

⇒ 인접한 chunk와 병합되지 않음

Small bin

• size가 다른 63개의 chunk를 각각 double linked list로 관리(FIFO)

• chunk의 size가 512byte 이하

• 해제가 되면 다음 chunk의 prev in use bit clear

⇒ 인접한 freed chunk와 병합

large bin

• 특정 범위의 size가 다른 63개의 chunk를 double linked list로 관리(FIFO)

• 크기가 512byte 이상 되는 chunk

• 범위 내에서 size가 가장 큰 chunk가 제일 앞

• 해제가 되면 chunk의 prev in use bit clear

⇒ 인접한 free chunk와 통합

• 다른 크기의 chunk를 가리키는 ptr fd_nextsize, bx_nextsize가 존재

unsorted bin

unsorted bin에 들어가는 경우

• free 했을 때 각 bin(small bin, large bin)으로 들어가기 전

• fast bin 들이 병합(malloc_consolidate)되어 합쳐지면

⇒ malloc_consolidate : 큰 chunk의 크기를 요청받았을 때 fast bin에 포함된 chunk들을 합침

• best fit으로 할당된 chunk의 남은 부분인 remainder

⇒ free된 chunk가 140byte인데 100byte를 할당하면 남은 40byte는 unsorted bin에 할당

• 인접한 chunk가 이미 free되어 있고 해당 chunk가 free될 때 두개의 free chunk가 병합됨

⇒ 병합된 free_chunk가 unsorted bin에 들어감

unsorted bin에서 나오는 경우

• 사용자가 malloc을 호출하여 요청한 size와 동일한 chunk가 있으면

Consolidate

• 해제하려는 chunk의 앞, 뒤 chunk가 이미 해제되어 있을 때 발생

• 병합되는 부분에 속한 free chunk의 fd, bk 정리 ⇒ unlink

  • bin list에 등록된 chunk를 제거하기 위해서 포인터를 정리하는 작업

참고한 사이트

heap basic Youtube영상

회고

지난 회차 내용과 지번 회차 내용을 구글 프레젠테이션으로 정리해보았다.

heap