Heap - ptmalloc2 (glibc)

ptmalloc2

---

1. ptmalloc2

1. ptmalloc2 ?

ptmalloc2 (pthread malloc 2) 는 Memory Allocator 이다

리눅스에서 사용하고 있으며, Glibc 에 구현되어 있다

 

ptmalloc 의 구현 목표는 효율적인 메모리 관리이다

• 메모리 낭비 방지
• 빠른 메모리 재사용
• 메모리 단편화 방지

ptmalloc 의 메모리 관리 전략을 알아보자

 

2. 메모리 낭비 방지

메모리 동적 할당과 해제는 매우 자주 일어나게 된다

컴퓨터의 메모리는 한정적이기 때문에 매 번 새로운 메모리 공간을 할당할 수 없다

 

ptmalloc 은 메모리 할당 요청이 발생하면, 해제된 메모리 공간 중에 재사용할 수 있는 공간이 있는지 탐색한다

해제된 메모리 공간 중에서 요청된 크기와 같은 크기의 메모리 공간이 있다면 그대로 재사용한다

작은 크기의 할당 요청이 발생했을 때 해제된 메모리 공간 중 큰 메모리 공간 영역을 나눠주기도 한다

 

3. 빠른 메모리 재사용

운영체제가 프로세스에 제공하는 가상 메모리 공간은 매우 넓다

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

→ ptmalloc 은 메모리 공간을 해제할 때 tcache 또는 bin 이라는 연결 리스트에 해제된 공간의 정보를 저장한다

 

tcache 와 bin 은 여러 개가 정의되어 있고 각각 서로 다른 메모리 크기의 공간을 저장한다

특정 크기의 할당요청이 발생할 때 그 크기와 관련된 저장소만 탐색하면 돼서 메모리를 효율적으로 사용할 수 있다

 

4. 메모리 단편화 방지

메모리 단편화는 크게 내부 단편화와 외부 단편화로 나뉘게 된다

 

내부 단편화

• 할당한 메모리 공간의 크기보다 실제 데이터가 점유하는 공간이 적을 때 발생한다

외부 단편화

• 할당한 메모리 공간들 사이에 공간이 많아서 생기는 비효율이다

단편화가 심해질수록 각 데이터 사이에 공간이 많아져서 메모리 사용 효율이 감소한다

 

단편화 ? 

전체 메모리 용량은 충분하지만 필요한만큼 연속된 공간이 없어서 할당 실패가 발생하는 현상이다

 

ptmalloc 은 이러한 단편화를 방지하기 위해 정렬(alignment), 병합(coalescence), 분할(split)을 사용한다

• 정렬(alignment)
  ptmalloc 은 메모리 공간을 16바이트 단위로 할당한다
  1~16byte 를 요청하면 16byte 를 할당하고 17~32byte 를 요청하면 32byte 를 할당한다
  → 16 바이트 이내의 내부 단편화가 발생할 수 있지만 외부 단편화를 감소시킬 수 있다
  
  비슷한 크기의 요청이 발생할 확률이 높기 때문에 비슷한 크기의 요청은 같은 크기의 공간을 반환해
  해제된 청크의 재사용률을 높일 수 있다

 

• 병합(coalescence)
  특정 조건을 만족하면 해제된 공간들을 병합해서 큰 크기의 요청에 반환한다

 

• 분할(split)
  작은 크기의 요청에는 큰 크기의 공간을 분할해서 재사용한다

 

 

2. 청크 (Chunk)

1. 청크 (Chunk)

청크(Chunk) 는 ptmalloc 이 할당한 메모리 공간을 의미한다

청크는 헤더와 데이터로 이루어져있다

헤더는 청크 관리에 필요한 정보를 담고 있고, 데이터 영역에 사용자가 입력한 데이터가 저장된다

 

사용중인 청크(왼쪽) 해제된 청크(오른쪽)

헤더는 청크의 상태를 나타내기 때문에 사용중인 청크(in-use)의 헤더와 해제된 청크(freed) 의 헤더는 구조가 다르다

해제된 청크는 data 가 있던 부분에 fd, bk 가 덮어씌워지게 된다

 

청크 헤더의 각 요소를 알아보자

• pre_size
  • 인접한 직전 청크의 크기이다
  • 청크를 병합할 때 사용된다
• size
  • 현재 청크의 크기이다
  • 헤더의 크기도 포함된 값이다
  • 메모리 단편화를 방지를 위해 x86 에서는 8byte, x64 에서는 16byte 단위로 정렬된다
    → size 의 하위 4bit 가 0 이 되게 된다
    ptmalloc 은 하위 4bit 중 3bit 를 flag로 사용을 하고 있다 (실제 크기를 계산할 때는 제외된다)
• flags
  • prev_inuse - 이전 chunk 가 사용중이라는 표시
    → 이전 chunk 가 할당됐으면 1 아니면 0 (첫 번째 청크는 1로 고정한다)
  • is_mmapped - chunk 가 mmap 으로 할당됐는지
    → mmap 으로 할당됐으면 1 아니면 0
  • non_main_arena - 메인 arena 가 아닌 곳에서 할당됐는지
    → arena 는 힙을 관리하는 구조체. main_arena 에서 할당됐으면 1 아니면 0
• fd - 연결리스트에서 다음 청크를 가리킨다 (해제된 청크에만 존재)
• bk - 연결리스트에서 이전 청크를 가리킨다 (해제된 청크에만 존재)

 

2. 청크 (Chunk) 의 종류

#include <stdio.h>
#include <stdlib.h>

int main() {
    char *chunk = malloc(0x30);
    *chunk = 'a';

    free(chunk);
    return 0;
}

위의 코드를 실행하고 heap 영역을 확인해보자

 

1. Allocated Chunk (사용 중인 청크)

사용 중인 청크

malloc 으로 0x30 을 요청하고 heap 영역을 확인해보면 size 가 0x41 인 것을 볼 수 있다

요청한 크기 (0x30) + 헤더 크기(0x10, 16byte) 를 생각하면 0x40 이 나와야 한다

 

그런데 왜 0x41 의 값이 들어갈까?

위에서 flag 를 설명할 때 첫 번째 청크는 prev_inuse 의 값이 1 로 설정된다고 했다

따라서 0x1 이 더해져서 0x41 이 size 가 되게 된다

 

그 다음으로는 a 의 값인 0x61이 들어간 것을 확인할 수 있다

 

2. freed chunk (해제된 청크)

free 로 메모리를 해제한 뒤 heap 영역을 확인해보자

해제된 청크

data 가 들어있던 부분에 fd 와 bk 의 값이 생긴 것을 볼 수 있다

원래 있던 data 의 첫 8byte 와 다음 8byte 는 fd 와 bk 로 덮어씌워지는 것을 알 수 있다

 

3. Top chunk

탑 청크

top chunk 는 heap 영역의 가장 마지막에 위치한다

아직 사용되지 않은 청크로 malloc 요청이 왔을 때 여기서 잘라서 할당한다

heap 에 충분한 공간이 없다면 top chunk 를 확장해서 추가적인 메모리를 할당한다

 

첫번째 Allocated chunk 의 0x290 의 크기는 tcache 와 관련된 것이다

 

 

3. bin

1. bin ?

bin 은 사용이 끝난 청크들이 저장되는 곳이다

메모리의 낭비를 막고 해제된 청크를 빠르게 재사용 할 수 있도록 한다

 

bin 은 다음과 같은 종류가 있다

• smallbin (62개)
• fastbin (10개)
• largebin (63개) 
• unsortedbin (1개)

 

2. smaillbin

	x86	x64
크기	16 ~ 512 byte 미만	32 ~ 1024 byte 미만
정렬	8 byte	16 byte
smallbin[0]	16 byte	32 byte
smallbin[61]	496 byte	1008 byte

• smallbin은 원형 이중 연결 리스트이다
• 하나의 smallbin 에는 같은 크기의 청크들만 보관된다
• 청크를 FIFO (First In First Out) 방식으로 사용된다
  → 먼저 해제된 청크가 먼저 재할당 되는 방식이다
• 이중 연결 리스트의 특성 때문에 smallbin 에 청크를 추가하거나 꺼낼 때 연결 고리를 끊는 과정이 필요하다
  → 이 과정을 unlink 라고 한다 (연결 해제 과정)
• 해제 될 때 인접한 메모리에 해제된 청크가 있다면 병합된다
  → 이 과정을 consolidation 이라고 한다

unlink ? 

해제된 청크를 병합할 때 청크에 있는 fd와 bk 를 정리하는데 이 작업을 unlink 라고 한다

 

3. fastbin

일반적으로 크기가 작은 청크들이 큰 청크들보다 자주 할당되고 해제된다

이런 이유로 ptmalloc 은 어떤 크기를 정해두고, 이 크기보다 작다면 smallbin 이 아닌 fastbin 에 저장한다

fastbin 에 저장된 청크들은 메모리 단편화보다 속도를 좀 더 우선순위에 두게 된다

 

	x86	x64
크기	10 ~ 64 byte 이하	32 ~ 128(176) byte 이하
정렬	8byte	16 byte
개수	10개가 있지만 작은 크기부터 7개만 사용한다	10개가 있지만 작은 크기부터 7개만 사용한다

• fastbin은 단일 연결 리스트이다
  → 청크를 꺼낼 때 꺼낸 앞과 뒤를 꺼내는 unlink 과정을 하지 않아도 된다
• 속도가 빨라야 하기 때문에 파편화가 심한 LIFO(last In First Out) 의 방법으로 사용된다
  → 나중에 해제된 청크가 먼저 재할당된다
• fd 포인터만 사용한다
• fastbin에 저장되는 청크들은 서로 병합되지 않는다
  → 청크 간 병합에 사용되는 연산도 아낄 수 있다
       청크가 해제되어도 다음 청크의 prev_inuse 값이 변경되지 않는다

 

4. largebin

	x86	x64
크기	512 byte 이상	1024 byte 이상
largebin[0]	512 ~ 576 byte 미만	1024 ~ 1088 byte 미만
largebin[32]	1536 ~ 2048 byte 미만	3072 ~ 3584 byte 미만

• smallbin, fastbin 과 달리 largebin 에서 일정 범위 안의 크기를 갖는 청크들을 모두 보관한다
  → 적은 수의 largebin 으로 다양한 크기를 갖는 청크들을 관리할 수 있다
• largebin은 범위에 해당하는 모든 청크를 보관하기 때문에 재할당 요청이 발생했을 때
  ptmalloc은 크기가 가장 비슷한 청크(best-fit)를 꺼내서 재할당 한다
• largebin은 이중 연결 리스트이기 때문에 재할당 과정에서 unlink 도 동반된다
• 연속된 largebin 청크들은 병합의 대상이 되고 병합된 청크는 unsortedbin 에 들어간다

정렬 포인터

• 청크를 내림차순으로 정렬해서 관리한다
  → 이 때 fd_nextsize, bk_nextsize 포인터가 사용된다
• 가장 앞쪽에 있는 청크만 fd_nextsize, bk_nextsize 를 가진다
• fd_nextsize 로 갈수록 청크의 크기가 작아진다
• bk_nextsize 로 갈수록 청크의 크기가 커진다
• 새로운 청크가 들어갈 때 가장 앞으로 들어가지만 fd_nextsize 영역의 앞에는 들어가지 않는다

mmap 사용

• 128kb 이상의 공간이 할당되는 경우 mmap() 시스템 콜을 통해 별도의 공간을 할당한 뒤 청크가 생성된다
  청크는 bin 에 들어가지 않고 is_mmapped flag 가 1로 설정된다
• 해제 시 mumap() 을 사용한다

 

5. unsortedbin

• unsortedbin 은 분류되지 않은 청크들을 보관하는 bin이다
• unsortedbin 은 하나만 존재한다
• fastbin 에 들어가지 않는 모든 청크들은 해제되었을 때 크기를 구분하지 않고 unsortedbin에 저장된다
• unsortedbin 은 원형 이중 연결 리스트이고 내부적으로 정렬, 분류되지 않는다
• smallbin 크기에 해당하는 청크를 할당 요청하면
  → ptmalloc 은 fastbin 이나 smallbin 을 탐색한 뒤 unsortedbin 을 탐색한다
• largebin 크기에 해당하는 청크를 할당 요청하면
  → unsortedbin 을 먼저 탐색한다
• unsortedbin 에서 적절한 청크가 발견되면 해당 청크를 사용한다
  → 이 과정에서 탐색된 청크들은 크기에 따라 적절한 bin 으로 분류된다

 

 

4. arena

arena 는 heap 영역 전체를 관리하는 구조체로 fastbin, samllbin, largebin 등의 정보를 모두 담고 있는 구조체이다

arena 는 크게 main arena 와 sub arena 로 나뉜다

 

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

→ 레이스 컨디션을 막을 수 있지만 병목 현상이 생길 수 있다

 

pamalloc 은 병목을 최대한 피하기 위해 최대 64개의 arena 를 생성할 수 있다

arena 에 락이 걸려서 대기해야 하는 경우 새로운 arena 를 만들어 이를 피할 수 있다

→ 생성할 수 있는 갯수가 64개로 제한되어 있기 때문에 결국 병목 현상이 발생하게 된다

 

그래서 glibc 2.26 에서 tcache 가 도입되었다

 

레이스 컨디션?

레이스 컨디션은 공유 자원을 여러 쓰레드나 프로세스에서 접근할 때 발생하는 오작동이다

한 쓰레드가 어떤 정보를 참조하고 있을 때 다른 쓰레드가 그 정보를 삭제하면

참조하고 있던 쓰레드는 삭제된 정보를 참조하게 된다

 

이런 레이스 컨디션을 막기 위해 락(Lock) 기능을 제공한다

한 쓰레드에서 어떤 자원에 락을 걸면 다른 쓰레드는 락이 해제될 때까지 기다려야 한다

→ 사용하는 동안은 락을 걸어 놓기 때문에 다른 쓰레드에 의한 조작이 차단된다

 

하지만 락은 쓰레드를 무제한으로 대기시키기 때문에 쓰레드의 수가 많아지면 병목 현상이 일어날 수 있다

락으로 발생하는 대표적인 문제 중 하나가 데드락이다

→ 두 쓰레드가 서로의 락 해제를 기다리며 무한으로 대기하게 되는 문제이다