동적 할당이 어떻게 진행되는지 정리
List of Contents
데이터를 할당하는 방법 (스택 / 힙)
스택에 할당된 데이터
스택에 할당되는 데이터는 지역변수로 선언된 데이터들이 들어갑니다. 일반적으로 함수 안에서 선언한 데이터들이 지역변수에 해당됩니다. 아래 코드에서 a 변수가 지역변수에 해당됩니다. 해당 변수에 들어가는 정수 8은 스택영역에 저장됩니다.
1
2
3
4
5
6
7
8
9
#include <stdio.h>
#include <stdio.h>
int main() {
int a = 8;
return 0;
}
아래 사진을 보면 8이 스택영역에 들어가있는 것을 확인 가능합니다. 지역변수의 lifetime은 해당 지역변수가 선언된 함수가 return될때 해제됩니다.
힙에 할당된 데이터
지역변수나 전역변수의 경우, 데이터 타입에 따라서 변수의 사이즈가 컴파일 과정에서 결정됩니다. 이렇게 컴파일 과정에서 선언이 되는 변수의 사이즈는 고정값으로 변경하지 못합니다.
하지만 컴파일 때가 아닌, 런타임 중에 변수의 사이즈가 결정되는 경우가 있는데 바로 힙이 이에 해당합니다. 힙 영역에 데이터를 저장하게 되면, 이는 런타임시에 데이터 사이즈가 결정되고, Lifetime 또한 런타임에만 알 수 있습니다(Ex: free).
1
2
3
4
5
6
7
8
9
10
11
12
#include <stdio.h>
#include <stdlib.h>
int main() {
int a;
scanf("%d", &a);
int* test = (int*)malloc(a);
*test = 5;
printf("%d\n", *test);
return 0;
}
위 코드를 보면 사용자에게 입력을 받는 사이즈만큼 malloc을 호출합니다. 이 부분이 바로 런타임시에 사용자의 입력에 따라서 사이즈가 달라지는 부분이므로 컴파일에서는 사이즈를 알 수 없다는 뜻입니다.
malloc이 반환하는 주소는 실제 데이터를 담을 수 있는 첫 시작 주소를 리턴하게 되고, 이게 위 사진에서 test 포인터 변수에 들어가게 됩니다.
위 사진이 실제 힙 영역입니다. *test = 5; 까지 진행을 한 후 메모리를 보면 위 사진과 같이 5가 **0x1aac420** 주소에 들어가 있는걸 확인할 수 있습니다. 바로 이 주소를 malloc이 수행되고 반환해주는 것입니다.
Heap 기초
Dynamic memory allocator
위에서 동적으로 할당된 메모리는 힙 영역에서 관리된다고 알아봤습니다. 이렇게 동적으로 할당된 메모리를 관리하기 위해서 운영체제는 dynamic memory allocator를 사용합니다.
Allocator는 크게 두 종류로 나뉩니다.
Explicit allocator : 개발자가 공간의 할당/해제를 관리
Ex) libc의 malloc과 free
Implicit allocator : 개발자는 공간의 할당만 담당하고 free는 내부적으로 처리
Ex) Java의 GC, Lisp 등
Explicit allocator에는 여러가지 종류가 있습니다. 아래에서 간단하게 알아보겠습니다.
dlmalloc
리눅스 초창기에 사용된 기본 메모리 할당자입니다. dlmalloc에서 동일한 시간에 2개의 쓰레드가 malloc을 호출할 경우, freelist 데이터는 모두 사용가능한 쓰레드에 둘러쌓인 상태로 공유되기 때문에 오로지 하나의 쓰레드만 임계영역에 들어갈 수 있습니다. 때문에 다중 쓰레드 앱에서는 성능저하가 발생합니다.
ptmalloc2
dlmalloc에서 쓰레딩 지원기능이 추가된 할당자입니다. ptmalloc2는 glibc 소스 코드에 통합됐습니다. 동일한 시간에 2개의 쓰레가 malloc을 호출할 경우, 메모리는 각각의 쓰레드가 분배된 힙 영역을 일정하게 유지하고, 힙을 유지하기 위한 freelist 데이터 또한 분배되어 있기 때문에 즉시 할당됩니다.
Jemalloc
단편화 방지 및 동시 확장성을 강조한 할당자입니다. Jason Evnas가 만들었고, 페이스북이나 파이어폭스에서 주로 사용합니다.
tcmalloc
구글이 만든 성능 도구에 포함되어 있는 힙 메모리 할당자로서 크롬 및 많은 프로젝트에서 사용합니다. 멀티 쓰레드 환경에서 메모리 풀을 사용하는 속도를 개선하기 위한 목적으로 만들어졌습니다. 즉, 어플리케이션에서 따로 쓰레드 별로 메모리 풀 관리를 하지 않아도 되게 구현되어있습니다.
Glibc malloc (2.23기준)
gblic에서 사용하는 ptmalloc2에 대해서 자세히 알아보겠습니다. 단순 익스플로잇만을 위한 힙 공부가 아닌 힙의 구조를 이해하고 어떤 식으로 운영체제에서 malloc이 작동하는지 위주로 공부하려고 노력했습니다.
위에 설명에서 ptmalloc2은 동일한 시간에 2개의 쓰레드가 malloc을 호출할 경우, 메모리는 각각의 쓰레드가 분배된 힙 영역을 일정하게 유지하고, 힙을 유지하기 위한 freelist data structures 또한 분배되어 있기 때문에 즉시 할당된다고 했습니다. 이렇게 각각의 쓰레드의 유지를 위해 분배된 힙과 freelist data structures의 행동을 per thread arena라고 부릅니다.
dlmalloc에서 쓰레드 기능이 추가된 것이 ptmalloc2이라고 했는데, ptmalloc2에서 쓰레드 관련 처리가 어떻게 진행되는지 코드로 알아보겠습니다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
#include <unistd.h>
#include <sys/types.h>
void* threadFunc(void* arg) {
printf("Before malloc in thread 1\n");
getchar();
char* addr = (char*) malloc(1000);
printf("After malloc and before free in thread 1\n");
getchar();
free(addr);
printf("After free in thread 1\n");
getchar();
}
int main() {
pthread_t t1;
void* s;
int ret;
char* addr;
printf("Welcome to per thread arena example::%d\n",getpid());
printf("Before malloc in main thread\n");
getchar();
addr = (char*) malloc(1000);
printf("After malloc and before free in main thread\n");
getchar();
free(addr);
printf("After free in main thread\n");
getchar();
ret = pthread_create(&t1, NULL, threadFunc, NULL);
if (ret) {
printf("Thread creation error\n");
return -1;
}
ret = pthread_join(t1, &s);
if (ret) {
printf("Thread join error\n");
return -1;
}
return 0;
}
디버깅하면서 확인 할 부분은 아래와 같습니다.
- main thread에서 malloc 호출 이전
- main thread에서 malloc 호출 이후, free 호출 이전
- main thread에서 free 호출 이후
- thread 생성후, 생성한 쓰레드에서 malloc 호출 이전
- 생성한 쓰레드에서 malloc 호출 이후, free 호출 이전
- 생성한 쓰레드에서 free 호출 이후
6가지 상태에서 힙 관리가 어떤식으로 진행되는지 확인해보겠습니다.
main thread에서 malloc 호출 이전
위 사진은 main()에서 malloc이 호출되기 전 메모리 상태입니다. pthread_create가 진행되지 않았으므로 메인 쓰레드 밖에 없는 것을 확인할 수 있습니다. 그리고 아직 힙 영역도 할당되지 않은것도 확인할 수 있습니다.
main thread에서 malloc 호출 이후, free 호출 이전
malloc으로 힙이 할당되고, free되기 전 메모리 상태입니다. 힙 영역이 0xb8b000 ~ 0xbac000(0x21000)에 생성된 것을 확인할 수 있습니다. 이건 brk syscall을 사용하여 program break 위치를 증가시킴으로 확장된 영역입니다.
gef> catch syscall brk 명령어를 이용하여 brk에 bp를 걸고 malloc 함수가 호출되면 malloc이 실행되는 과정에서 brk syscall이 호출되는 것을 확인 할 수 있습니다.
malloc시 1000바이트만 요청했으나, 힙 메모리의 크기는 135168바이트(0x21000)나 생성되었습니다. 이러한 힙에 인접한 지역을 arena라고 부릅니다. 이 arena는 메인 쓰레드로 생성되었기 때문에 main arena라고 부릅니다.
이후, malloc을 통한 요청은 이 arena를 사용하여 해당 영역이 다 찰때까지 알아서 사용합니다. 만약 arena가 다 찰경우, 프로그램의 break위치를 증가시켜서(데이터 영역 확장) 관리를 합니다. 즉, Top chunk의 크기를 증가시켜 여분의 공간을 가지도록 확장하는 것입니다.
main thread에서 free 호출 이후
위 사진을 보면 heap 메모리 영역에 아무런 변화가 없는걸 확인할 수 있습니다. 즉 free가 호출되어 메모리가 해제되어도 바로 운영체제에 반환하지 않는다는 뜻입니다. 할당된 메모리의 일부분(100바이트)을 main_arena의 bin에 이 해제된 청크를 추가하고, glibc malloc 라이브러리에 반환됩니다.
해제후 사용자가 다시 메모리를 요청하는 경우, 아까와 같이 brk syscall로 할당해주는것이 아닌, bin에 비어있는 청크가 있는지 탐색하고, 존재한다면 비어있는 청크를 할당해줍니다. 만약 비어있는 청크가 없다면 아까와 같이 동일하게 메모리를 할당해줍니다.
thread 생성후, 생성한 쓰레드에서 malloc 호출 이전
pthread_create 함수를 통해 ID값이 2인 쓰레드가 생성되었습니다(thread2라고 하겠습니다). thread2는 threadFunc함수를 실행하는데 위 영역은 아직 malloc을 호출하지 않았으므로 thread2의 힙영역은 없지만, thread2의 스택 영역은 생성된 걸 확인할 수 있습니다.
thread2의 스택영역 : 0x00007efd46772000 ~ 0x00007efd46f73000
생성한 쓰레드에서 malloc 호출 이후, free 호출 이전
thread2의 힙영역(0x00007efd40000000 ~ 0x00007efd40021000)이 생성된 걸 확인할 수 있습니다. 해당 영역은 brk를 사용해서 할당하는 main_thread와 달리 mmap을 사용하여 힙이 생성됩니다. threadFunc 함수에서 malloc이 호출되는 과정중에 mmap이 호출됩니다.
프로세스 주소 공간에 135KB의 영역이 rw권한으로 세팅되어, thread2를 위한 힙 영역으로 할당되었습니다. 이러한 메모리의 일부분을 thread_arena라고 부릅니다.
생성한 쓰레드에서 free 호출 이후
thread2에서도 free호출 이후 바로 메모리를 반환하지 않는것을 확인할 수 있습니다. 아까처럼 해제한 영역은 thread_arena의 bin에 해제된 청크를 추가하고 glibc malloc에 반환합니다.
위와 같은 과정으로 메인 쓰레드, 쓰레드들이 관리가 됩니다. 추가적으로 glibc malloc의 소스코드에서 아래와 같이 3개의 데이터 구조체를 확인할 수 있습니다.
heap_info 구조체(Heap_Header)
1
2
3
4
5
6
7
8
1.typedef struct _heap_info {
2. mstate ar_ptr; /* 현재 heap을 담당하고 있는 Arena */
3. struct _heap_info *prev; /* 이전 heap 영역 */
4. size_t size; /* 현재 size(bytes) */
5. size_t mprotect_size; /* mprotected(PROT_READ|PROT_WRITE) size(bytes) */
6. char pad[(-6*SIZE_SZ)&MALLOC_ALIGN_MASK]; /* 메모리 정렬 */
7. /* sizeof(heap_info) + 2*SIZE_SZ는 MALLOC_ALIGN_MASK의 배수 */
} heap_info;
thread_arena는 각 쓰레드들에 대한 힙 영역이기 때문에 힙 영역의 공간이 부족하면 새로운 영역에 추가로 할당(mmap사용)받기 때문에 여러개의 힙 영역을 가질 수 있습니다.
main_arena는 여러개의 힙을 가질 수 없습니다. main_arena의 공간이 부족한 경우, sbrk 힙영역은 메모리가 매핑된 영역까지 확장됩니다.
이런 힙 영역은 어떤 arena가 관리하고 있는지, 힙 영역의 크기가 어느정도인지, 이전에 사용하던 힙 영역의 정보가 어디에 있는지를 저장할 필요가 있습니다.
이런 정보를 저장하기 위한 구조체가 바로 위 구조체인 heap_info이며, 힙에 대한 정보를 저장하기 때문에 Heap_Header라고도 합니다(main_thread는 확장을 해서 쓰기 때문에 제외).
malloc_state 구조체(arena_Header)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
1.struct malloc_state
2.{
3. /* Serialize access. */
4. mutex_t mutex;
5.
6. /* Flags (formerly in max_fast). */
7. int flags;
8.
9. /* Fastbins */
10. mfastbinptr fastbinsY[NFASTBINS];
11.
12. /* topchunk의 base address */
13. mchunkptr top;
14.
15. /* 가장 최근의 작은 요청으로부터 분리된 나머지 */
16. mchunkptr last_remainder;
17.
18. /* 위에서 설명한대로 pack된 일반적인 bins */
19. mchunkptr bins[NBINS * 2 - 2];
20.
21. /* Bitmap of bins */
22. unsigned int binmap[BINMAPSIZE];
23.
24. /* 연결 리스트 */
25. struct malloc_state *next;
26.
27. /* 해제된 아레나를 위한 연결 리스트 */
28. struct malloc_state *next_free;
29.
30. /* 현재 Arena의 시스템으로부터 메모리 할당 */
31. INTERNAL_SIZE_T system_mem;
32. INTERNAL_SIZE_T max_system_mem;
33.};
위에 Heap_Header에서는 단순히 힙 영역에 대한 정보만을 저장했스비다. arena는 힙 영역에 대한 정보 중에서도 어떤 부분을 사용하면 되는지를 관리하기 때문에 이를 알고 있을 필요가 있습니다. malloc_state 구조체는 각 arena에 하나씩 주어지고, 해제된 chunk를 관리하는 연결리스트bin과 최상위 Chunk인 Top Chunk와 같은 arena에 대한 정보를 저장합니다. 이를 arena_header라고도 부릅니다.
단일 쓰레드 arena는 여러개의 힙을 가질 수 있지만, 이러한 모든 힙에 대해서는 오직 하나의 arena_header만 존재합니다.
참고로 thread_arena와 달리, main_arena의 arena header는 sbrk 힙 영역의 일부가 아니다. main_arena는 전역변수이며, libc.so의 데이터 영역에서 찾을 수 있다.
malloc_chunk 구조체(Chunk Header)
1
2
3
4
5
6
7
8
9
10
11
12
1.struct malloc_chunk {
2.
3. INTERNAL_SIZE_T prev_size; /* Size of previous chunk (if free). */
4. INTERNAL_SIZE_T size; /* Size in bytes, including overhead. */
5.
6. struct malloc_chunk* fd; /* double links -- used only if free. */
7. struct malloc_chunk* bk;
8.
9. /* large block에서만 사용하고 해당 bin list의 크기 순서를 나타냄 */
10. struct malloc_chunk* fd_nextsize; /* double links -- used only if free. */
11. struct malloc_chunk* bk_nextsize;
12.};
힙 영역은 사용자에 의해 할당되거나, 해제되거나 하면 Chunk라는 단위로 관리됩니다.
- prev_size : 바로 이전 청크의 크기를 저장
- size : 현재 청크크기를 저장
- fd, bk : malloc시 데이터가 들어가고, free시 fd, bk포인터로 사용
- fd(bk)_nextsize : large bin을 위해서 사용되는 포인터
- main_arena와 thread_arena를 그림으로 나타낸 경우(단일 힙 영역)
- thread_arena를 그림으로 나타낸 경우(여러 개의 힙 영역)
함수 호출 과정 알고리즘
- malloc 함수 호출 순서 : libc_malloc() → int_malloc() → sysmalloc()
- libc_malloc() 함수에서 사용하는 Thread에 맞게 Arena를 설정한 후, int_malloc() 함수 호출
- int_malloc() 함수에서는 재사용할 수 있는 bin을 탐색하여 재할당하고, 마땅한 bin이 없다면 top chunk에서 분리해서 할당
- top chunk가 요청한 크기보다 작은 경우, sysmalloc() 함수 호출
sysmalloc() 함수를 통해 시스템에 메모리를 요청해서 top chunk의 크기를 확장하고 대체
※ sysmalloc() 함수는 기존의 영역을 해제한 후, 새로 할당함
- free 함수 호출 순서 : libc_free() -> int_free() -> systrim() or heap_trim() or munmap_chunk()
- libc_free() 함수에서 mmap으로 할당된 메모리인지 확인한 후, 맞을 경우 munmap_chunk() 함수를 통해 메모리 해제
- 아닌 경우, 해제하고자 하는 chunk가 속한 Arena의 포인터를 획득한 후, int_free() 함수 호출
- chunk를 해제한 후, 크기에 맞는 bin을 찾아 저장하고 top chunk와 병합을 할 수 있다면 병합 수행
- 병합된 top chunk가 너무 커서 Arena의 크기를 넘어선 경우, top chunk의 크기를 줄이기 위해 systrim() 함수 호출
- 문제가 없다면, heap_trim() 함수 호출
- mmap으로 할당된 chunk라면 munmap_chunk()를 호출
