[Heap] ptmalloc2(pthread malloc 2)

Memory Allocator의 일종

리눅스에서 사용됨, GLibc에 구현됨

목표

메모리의 효율적인 관리

1. 메모리 낭비 방지

▶ 메모리 할당 요청이 발생하면

먼저, 해제된 메모리 공간 중에서 재사용할 수 있는 공간이 있는지 탐색

여기에 요청된 크기와 같은 크기의 메모리 공간이 있다면 이를 그대로 재사용

 

▶ 작은 크기의 할당 요청이 발생하면

해제된 메모리 공간 중 매우 큰 메모리 공간이 있는 경우 그 영역을 나누어 주기도

2. 빠른 메모리 재사용 

▶ 메모리 공간을 해제할 때, tcache 또는 bin이라는 연결 리스트에 해제된 공간의 정보를 저장해둠 

이유: 운영체제가 프로세스에게 제공해주는 가상 메모리 공간은 매우 넓으므로,

특정 메모리 공간을 해제한 이후에 이를 빠르게 재사용하려면 해제된 메모리 공간의 주소를 기억하고 있어야 함

 

▶ tcache와 bin은 여러 개가 정의되어 있으며, 각각은 서로 다른 크기의 메모리 공간들을 저장함

-> 특정 크기의 할당 요청이 발생했을 때, 그 크기와 관련된 저장소만 탐색하면 됨 -> 효율적

3. 메모리 단편화 방지 

▶ (64비트 환경에서) 메모리 공간을 16바이트 단위로 할당

: 사용자가 어떤 크기의 메모리 공간을 요청하면,
그보다 조금 크거나 같은 16바이트 단위의 메모리 공간 제공

eg. 4바이트를 요청하면 16바이트를, 17바이트를 요청하면 32바이트를 할당

-> 정렬 없이 딱 요청한 만큼 할당해주는 경우에 비해 오히려 외부 단편화가 감소하였음 

 

▶ 병합

병합으로 생성된 큰 공간은 그 크기와 같거나 작은 요청에 의해 분할되어 재사용됨

-> 해제된 공간의 재사용률을 높이고, 외부 단편화를 줄임

 

 

ptmalloc의 주요 객체

1. Chunk

 

: ptmalloc이 할당한 메모리 공간

 

▶ 구조

헤더 + 데이터

 

▶ 헤더

prev_size	8바이트	인접한 직전 청크의 크기 -> 청크를 병합할 때 직전 청크를 찾는 데 사용됨
size	8바이트	현재 청크의 크기 (헤더의 크기도 포함)
flags	3비트	allocated arena(A), mmap’d(M), prev-in-use(P) - prev-in-use: 직전 청크가 사용 중인지 -> 이를 참조해 병합이 필요한지 판단
fd	8바이트	연결 리스트에서 다음 청크를 가리킴. In-use 청크는 이를 사용하지 않고 이 위치에 데이터가 저장됨
bk	8바이트	연결 리스트에서 이전 청크를 가리킴. In-use 청크는 이를 사용하지 않고 이 위치에 데이터가 저장됨

 

▶ 데이터 영역

사용자가 입력한 데이터가 저장됨

 

2. Bin

: 사용이 끝난 청크들이 저장됨

-> 메모리의 낭비를 막고, 해제된 청크를 빠르게 재사용할 수 있게 됨

 

▶ 총 128개의 bin이 정의됨

이 중 62개는 smallbin, 63개는 largebin, 1개는 unsortedbin으로 사용, 나머지 2개는 사용 X

 

2.1. smallbin

: 32 바이트 이상 1024 바이트 미만의 청크 보관

 

▶ 하나의 smallbin에는 같은 크기의 청크들만 보관되며, index가 증가하면 저장되는 청크들의 크기는 16바이트씩 커짐

: smallbin[0]는 32바이트 청크를, smallbin[61]은 1008 바이트 청크를 보관

 

▶ 원형 이중 연결 리스트 (circular doubly-linked list)임

 

▶ FIFO 사용

먼저 해제된 청크가 먼저 재할당됨

 

▶ unlink

smallbin에 청크를 추가하거나 꺼낼 때, 이중 연결 리스트의 특성 상 연결 고리를 끊는 과정 필요

 

▶ 병합: consolidation

메모리상에서 인접한 두 청크가 해제되어 있고, 이들이 smallbin에 들어있으면 이 둘은 병합됨

 

▶ 할당, 해제, 병합 과정

 

2.2. fastbin

: 32바이트 이상 128바이트 이하의 청크 보관

 

▶ smallbin 외에도 fastbin이 따로 있는 목적 

일반적으로 크기가 작은 청크들이 큰 청크들보다 빈번하게 할당되고 해제되므로,

작은 청크들의 할당과 해제가 효율적이어야 전체적인 효율성이 높아짐

 

▶ 단일 연결 리스트임

 

▶ 청크 꺼낼 때 unlink 불필요 

단일 연결 리스트라서

 

▶ LIFO 사용

나중에 해제된 청크가 먼저 재할당됨

-> 속도는 빠르지만 다른 방법에 비해 파편화가 심함

 

▶ fastbin에 저장되는 청크들은 서로 병합되지 않음

-> 청크 간 병합에 사용되는 연산이 절약됨

 

▶ 할당과 해제 과정

2.3. largebin

: 1024 바이트 이상의 청크 보관

 

▶ 총 63개의 largebin 존재

 

▶ 각 largebin은 일정 범위 내 크기의 청크들을 모두 보관

이 범위는 largebin의 인덱스가 증가하면 로그적으로 증가

eg. largebin[0]는 1024 바이트 이상 1088 바이트 미만, largebin[32]는 3072 바이트 이상 3584 바이트 미만의 청크 보관

-> 적은 수의 largebin으로 다양한 크기를 갖는 청크들을 관리할 수 있음

 

▶ 이중 연결 리스트임

 

▶ 재할당

largebin은 범위에 해당하는 모든 청크를 보관하므로,

재할당 요청 발생 시 ptmalloc은 그 안에서 크기가 가장 비슷한 청크 (best-fit)를 꺼내 재할당함

이 과정을 빠르게 하기 위해, ptmalloc은 largebin 안의 청크를 크기 내림차순으로 정렬함

 

▶ 이중 연결 리스트 -> 재할당 시 unlink 필요

 

▶ 병합

연속된 largebin 청크들은 병합됨

2.4. unsortedbin

: 분류되지 않은 청크 보관

(fastbin에 들어가지 않는 모든 청크들은 해제 시 크기를 구분하지 않고 unsortedbin에 보관됨)

 

▶ unsortedbin은 하나만 존재

 

▶ 원형 이중 연결 리스트. 정렬은 X

 

▶ 할당

smallbin 크기의 청크 할당 요청 -> fastbin 탐색 -> smallbin 탐색 -> unsortedbin 탐색 -> sysmalloc

largebin 크기의 청크 할당 요청 -> unsortedbin 탐색 -> laragebin 탐색 -> sysmalloc

 

▶ unsortedbin의 필요성

: 불필요한 연산을 줄이고, 성능을 최적화

3. arena

: fastbin, smallbin, largebin 등의 정보를 모두 담고 있음

 

멀티 쓰레드 환경에서 ptmalloc은 레이스 컨디션을 막기 위해 arena에 접근할 때 arena에 Lock을 적용

-> 문제: 병목 현상 발생

-> 완화: 최대 64개의 arena를 생성할 수 있게 함 - arena에 락이 걸려서 대기해야 하는 경우, 새로운 arena를 생성해 병목 완화

 

4. tcache(thread local cache)

: 각 쓰레드에 독립적으로 할당되는 캐시 저장소

: 32 바이트 이상 1040 바이트 이하의 청크 보관
이 범위의 청크들은 할당 및 해제 시 tcache를 가장 먼저 조회 -> tcache가 가득찼다면 적절한 bin으로 분류됨

 

▶ 도입 목적

arena의 최대 개수가 64개로 제한돼있으므로, 과도한 멀티 쓰레드 환경에서는 여전히 병목 현상 발생

이떄 arena의 bin에 접근하기 전에 tcache를 먼저 사용하면, arena에서 발생할 수 있는 병목 현상이 완화됨 

-> 멀티 쓰레드 환경에 더욱 최적화된 메모리 관리 메커니즘을 제공

 

▶ 각 쓰레드가 고유하게 갖는 캐시임 -> ptmalloc은 레이스 컨디션을 고려하지 않고 이 캐시에 접근할 수 있음

 

▶ 각 쓰레드는 64개의 tcache를 가짐

 

▶ 하나의 tcache는 같은 크기의 청크들만 보관

 

▶ 각 tcache에 보관할 수 있는 청크의 갯수를 7개로 제한
∵ 쓰레드마다 정의되는 tcache의 특성 상, 무제한으로 청크를 연결할 수 있다면 메모리 낭비 위험 있음

 

▶ 단일 연결 리스트임

 

▶ LIFO 방식

 

▶ tcache 청크들은 병합 X

 

▶ 보안 검사가 많이 생략돼 있음 -> 힙 익스플로잇 위험 

 

▶ 메모리 할당, 해제 과정