Memory Allocator
운영체제에서 한정된 메모리 자원을 각 프로세스에 효율적으로 분배하는 프로그램이다.
종류
- ptmalloc2 : 리눅스
- tcmalloc : 구글
- jemalloc : 페이스북, 파이어폭스
ptmalloc의 이점
1. 메모리 낭비 방지
최근 해제된 메모리 공간중 재사용할 수 있는 공간이 있는지 탐색한다.
작은 크기의 할당 요청이 발생했을 때, 해제된 공간 중 매우 큰 메모리 공간이 있으면 영역을 나누어 주기도한다.
2. 빠른 메모리 재사용
특정 메모리 공간이 해제된 이후 이를 빠르게 재사용하려면 메모리 공간의 주소를 기억하고 있어야한다.
따라서 tcache와 bin은 여러 개가 정의되어 있으며, 각각은 서로 다른 크기의 메모리 공간들을 저장한다.
3. 메모리 단편화 방지
메모리 단편화에는 내부 단편화와 외부 단편화 이렇게 2개의 메모리 문제가 있다.
- 내부 단편화 : 할당한 메모리 공간의 크기에 비해 실제 데이터가 점유하는 공간이 적을 때
- 외부 단편화 : 할당한 메모리 공간들 사이에 공간이 발생하는 문제
ptmalloc은 정렬, 병합, 분할을 사용하여 단편화 문제를 해결할려 했습니다.
ptmalloc의 구성 요소
ptmalloc의 구성 요소에는
- chunk
- bin
- arena
- tcache 가 있으며 각각 메모리 할당에 필요한 구성 요소입니다.
Chunk
ptmalloc이 할당한 메모리 공간을 의미한다. 헤더와 데이터로 구성되며 헤더에는 관리에 필요한 데이터를 데이터에는 사용자가 입려한 데이터를 저장한다.
chunk의 경우 in-use 의 헤더와 해제된 청크의 헤더는 구조가 자소 다르다. in-use 상태의 경우 fd, bk영역이 없으며 freed의 경우 fd,bk가 존재한다.
| 이름 | 크기 | 설명 |
|---|---|---|
| prev_size | 8byte | 인접한 직전 청크의 크기를 저장함. |
| size | 8byte | 현재 청크의 크기를 저장함. |
| flags | 3bit | size의 하위 4비트는 의미가 없다. 따라서 ptmalloc에서는 size의 하위 3비트를 allocated arena, mmap’d, prev-in-use로 나타내며 청크 관리에 필요한 플래그 값으로 사용합니다. |
| fd | 8byte | 연결 리스트에서 다음 청크를 가르킴 (해제된 청크에만 존재) |
| bk | 8byte | 연결 리스트에서 이전 청크를 가르킴 (해제된 청크에만 존재) |
bin
사용이 종료된 청크들이 저장되는 객체이다. 해제된 청크를 빠르게 재사용 가능하게 도와준다.
ptmalloc에서는 128개의 bin이 정의되어 있으며, 62개의 smallbin과 63개의 largebin, 1개의 unsortedbin그리고 제일 위와 아래에 존재하는 2개는 사용되지 않는다.
smallbin
smallbin은 32byte 이상 1024byte 미만의 크기를 가진 청크들만 보관한다. index가 증가하면 저장되는 청크들의 크기는 16byte씩 커진다. 즉 smallbin[0]는 32byte, smallbin[61]은 1008byte이다.
smallbin은 원형 이중 연결 리스트이며, FIFO를 사용하여 해제된 청크를 먼저 재할당합니다.
Tip
청크 관리 알고리즘은 크게 3가지 방법이 있다.
- FILO : 선입 후출 stack에서 알고리즘이며, 속도가 빠르디만 파편화가 심하다.
- address-ordered : 정렬을 해야해서 속도는 느리지만 파편화가 적다.
- FIFO : FILO와 address-ordered 중간에 이점을 가지고 있다.
- unlink : 이중 연결리스트를 활용한 ptmalloc으 경우 청크를 추가하거나 꺼낼 때 연결 고리를 끊어야 한다.
- consolidation : 메모리상에서 인접한 두 청크가 해제되어 있으며, smallbin에 들어있다면 둘은 병합한다.
fastbin
크기가 작은 청크들이 큰 청크들보다 빈번하게 할당되고 해제된다. fastbin은 ptmalloc에서 정해둔 크기보다 작은 청크들을 저장합니다. 그리고 이런 빈번한 할당에서는 단편화보다 속도를 조금 더 우선순위로 둡니다.
Tip
fastbin에서는 LIFO 방법을 사용하며
unlink과정을 수행하지 않는다.
largebin
largebin은 1024byte 크기를 가진 청크들을 보관합니다. 63개의 largebin은 일정 범위 안에 크기를 갖은 청크들을 모두 보관합니다. 또한 인덱스가 증가하면 로그적으로 증가합니다.
largebin[0] : 1024 ~ 1088 byte largebin[32] : 3072 ~ 3584 byte
unsortedbin
unsortedbin은 분류되지 않은 청크들을 보관하는 bin이다. fastbin에 들어가지 않는 모든 청크들은 해제되었을 때 크기를 구분하지 않고 unsortedbin에 보관된다.
arena
arena는 fastbin, smallbin, largebin 등의 정보를 모두 저장하고 있는 객체이다. ptmalloc은 race condition 문제를 막기 위해 arena에 락을 적용한다. 하지만 race condition 문제를 해결하는 대신 병목 현상이 일어날 수 있다.
Tip
arena를 기존의 arena가 lock에 걸려있을 경우 새로운 arena를 생성해서 병목현상을 줄여줄 수 있습니다. 하지만 과도한 멀티스레드로 인한 arena 생성은 최대 값을 넘으면 병목 현상이 발생할 수 있습니다.
tcache
스레드에 독립적으로 할당되는 캐시 저장소이다.
각 스레드는 64개의 tcache를 가지고 있으며, fastbin과 같이 LIFO 방식을 활용합니다. 단일 연결 리스트이며, 하나의 tcache는 같은 크기의 청크들만 보관합니다. 청크의 개수를 7개로 제한하고 있으며, 이는 스레드마다 정의되는 tcache의 특성상, 무제한으로 청크를 연결할 수 있으면 낭비될 수 있기 때문입니다.
tcache는 스레드가 독립적으로 갖는 캐시이므로 ptmalloc은 레이스 컨디션을 고려하지 않고 캐시에 접근할 수 있습니다. 따라서 arena의 bin에 접근하기 전에 tcache를 먼저 사용하여 arena 병목 현상을 완화하는 효과가 있습니다.
정리
- ptmalloc : dlmalloc을 모태로 한 malloc, free, realloc 등을 기반으로 사용자의 동적 메모리 요청을 처리함.
- bins : 해제된 청크들의 보관함.
- arena : ptmalloc이 관리하는 메모리들의 정보 저장소
- tcache : 스레드마다 해제된 청크들의 보관소
- chunk : ptmalloc2가 메모리를 할당하는 단위