ptmalloc2 - 1

ptmalloc2?

리눅스에서는 malloc을 통해서 메모리 할당을 할 때에 내부적으로 ptmalloc이라는 함수가 실행된다. 앞으로 편의를 위해 malloc으로 지칭할 것이다.

목표
1. 메모리 낭비 방지
2. 빠른 메모리 재사용
3. 메모리 단편화 방지

구성 요소?

chunk

말 그대로 덩어리라는 뜻.
malloc을 통해 메모리를 할당하면 생기는 메모리 블럭.
64비트 architecture에서 16바이트 단위로 chunk가 할당된다.
기본적으로 header + data로 구성되어 있다.

header의 구성 요소

• prev_size
  • address space 상에서의 직전에 할당된 chunk의 크기.
• size
  • chunk 자신의 할당된 크기.
• flags
  • A(allocated arena)
    자신이 어느 arena에 속해있는지. 후에 서술 예정
  • M(mmapped)
    heap 영역인지 mmapped된 메모리인지. 후에 서술 예정
  • P(previous in use)
    address space 상에서의 직전 chunk가 사용중인지 free되었는지.
• fd
  • bin에서 연결리스트가 가리키는 forward chunk. free된 chunk에만 존재한다.
• bk
  • bin에서 연결리스트가 가리키는 backward chunk. free된 chunk에만 존재한다.

chunk의 구조

bin

사용이 끝난 chunk들이 저장된다.
빠른 재사용에 용이하다.
각 chunk의 크기별로 bin이 존재.
총 128개의 bin이 존재한다.

• 62개의 small bin
• 63개의 large bin
• 1개의 unsorted bin
• 2개는 사용되지 않는다.

각 bin들의 역할

• small bin
  • 크기 32 이상 1024 미만의 chunk들이 저장될 수 있다.
  • 각 bin에는 같은 크기들의 chunk들만 들어간다.
  • index가 증가할 수록 chunk들의 크기가 16바이트씩 커진다.
  • 자료구조 : circular doubly-linked list, FIFO
  • 병합 대상에 해당 : 인접한 두 chunk가 둘 다 free 상태이고, 둘 다 small bin에 위치해 있다면 둘은 병합된다. => consolidation 과정.
• large bin
  • 크기 1024이상의 chunk들이 저장된다.
  • small bin과 다르게, large bin의 경우에는 한 bin에 특정 범위에 해당하는 chunk들이 저장된다. (범위는 log scale로 증가함.)
  • 재할당은 크기가 가장 비슷한 chunk로 할당해 준다.
  • 자료구조 : doubly-linked list, 미리 내림차순으로 정리되어 있음
  • 연속된 large bin chunk들도 역시 병합 대상이다.
• fast bin
  • 크기가 작은 chunk들의 경우 더 빈번하게 할당 / 해제된다는 특성이 존재.
  • 그래서 이 chunk들을 더 빨리 할당 / 해제시켜주기 위해 별도로 fast bin을 두었다.
  • 크기 32 이상 176 이하의 범위, 총 10개가 존재한다. (리눅스의 경우 32 ~ 128 까지만 사용)
  • single-linked list, LIFO 사용 -> 속도가 더 빠르다.
• unsorted bin
  • 분류되지 않은 chunk들을 보관한다.
  • fastbin에 들어가지 않는 크기의 chunk들의 경우 우선적으로 unsorted bin에 보관한다.
  • 자료구조 : circular doubly-linked list, 정렬되어 있지 않음.

할당 시 동작 순서

• small bin 크기 요청 시 : fast bin / small bin 탐색 -> unsorted bin 탐색
• large bin 크기 요청 시 : unsorted bin 탐색 -> large bin 탐색
• unsorted bin을 탐색할 때, 해당 chunk의 크기에 해당하는 알맞은 bin으로 옮겨주는 역할을 한다.

arena

bin에 대한 정보를 비롯해서 malloc을 관리하는 데에 필요한 여러 정보가 담겨있는 구조체이다.
__malloc_hook + 0x10 의 메모리에 위치해 있다. (변수 명으로 찾을 수가 없다.)
멀티스레드의 경우 arena에 lock을 설정하여 동시에 접근할 수 없게 막아놓았다.
대신, 한 arena를 접근 시 lock이 걸려있다면, 다른 arena 객체를 생성해서 동작하게 되고, 최대 64개의 arena가 있을 수 있다.
하지만 이 경우에도 thread가 많은 경우 병목현상이 발생하고, 이를 해결하기 위해서 thread별로 tcache를 만들었다.

tcache

thread local cache.
각 스레드는 64개의 tcache를 가지고 있다.
하나의 tcache : 같은 크기의 chunk만 보관, 최대 7개까지 보관 가능.
크기 : 32 이상, 1040 이하
자료 구조 : single-linked list, LIFO
병합 여부 : x
할당 / 해제 시에 tcache를 가장 먼저 조회한다.

참고 자료

• https://learn.dreamhack.io/98