기본 콘텐츠로 건너뛰기

Heap-Memory

Heap-Memory

힙 메모리 이해하기

많은 메모리 할당자가 존재한다.

  • dlmalloc - 범용 할당 자
  • ptmalloc2 - glibc
  • jemalloc - FreeBSD와 Firefox
  • tcmalloc - Google
  • libumem - 솔라리스

모든 메모리 할당자는 빠르고 확장 가능하며 효율적이라고 주장하지만 모든 할당자가 개발하고자하는 어플리케이션에 적합할 수 는 없다. 메모리 사용량이 많은 응용 프로그램의 성능은 메모리 할당자 성능에 크게 좌우된다. 이 글에서는 glibc malloc 할당자에 대해서만 이야기하고자 한다.

ptmalloc2dlmalloc에서 분기되었다. fork후 스레딩 지원이 추가되어 2006년에 릴리즈되었다. 공식 릴리즈 후 ptmalloc2glibc 소스 코드에 통합되었다.

System call

시스템 호출: malloc은 내부적으로 brk 또는 mmap 시스템 호출을 한다.

Threading

스레딩: 리눅스 초기에는 dlmalloc이 기본 메모리 할당자로 사용되었다. 하지만 나중에 ptmalloc2의 스레딩 지원으로 리눅스 용 기본 메모리 할당자가 변경되었다. 스레딩 지원은 메모리 할당자 성능 및 응용 프로그램 성능을 향상시키는 데 도움이 된다. dlmalloc에서 두 개의 스레드가 동시에 malloc을 호출 할 때, freelist 데이터 구조가 사용 가능한 모든 스레드간에 공유되기 때문에 하나의 스레드 만 임계 섹션에 들어갈 수 있었다. 따라서 다중 스레드 응용 프로그램에서 메모리 할당에 시간이 걸리므로 성능 저하를 유발한다. ptmalloc2에서 두 스레드가 동시에 malloc을 호출하는 동안 각 스레드는 별도의 힙 세그먼트를 유지하므로 이 힙을 유지하는 freelist 데이터 구조도 분리되어 메모리를 즉시 할당할 수 있다. 각 스레드에 대해 별도의 힙 및 freelist 데이터 구조를 유지하는 이 작업을 스레드 별 영역 이라고 한다.

예시

/* Per thread arena example. */
#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;
}
  • 메인 스레드에서 malloc하기 전: 스레드(thread 1)가 아직 생성되지 않았기 때문에 아직 힙 세그먼트가 없고 스레드 당 스택이 없음을 볼 수 있다.
$ gcc -pthread -o heap ./heap.c 
$ ./heap
Welcome to per thread arena example::2967
Before malloc in main thread
$ cat /proc/2967/maps
00400000-00401000 r-xp 00000000 08:01 414686                             /home/osboxes/workspace/heap
00600000-00601000 r--p 00000000 08:01 414686                             /home/osboxes/workspace/heap
00601000-00602000 rw-p 00001000 08:01 414686                             /home/osboxes/workspace/heap
7fd0263c6000-7fd02657b000 r-xp 00000000 08:01 790878                     /lib/x86_64-linux-gnu/libc-2.15.so
7fd02657b000-7fd02677b000 ---p 001b5000 08:01 790878                     /lib/x86_64-linux-gnu/libc-2.15.so
7fd02677b000-7fd02677f000 r--p 001b5000 08:01 790878                     /lib/x86_64-linux-gnu/libc-2.15.so
7fd02677f000-7fd026781000 rw-p 001b9000 08:01 790878                     /lib/x86_64-linux-gnu/libc-2.15.so
7fd026781000-7fd026786000 rw-p 00000000 00:00 0 
7fd026786000-7fd02679e000 r-xp 00000000 08:01 790958                     /lib/x86_64-linux-gnu/libpthread-2.15.so
7fd02679e000-7fd02699d000 ---p 00018000 08:01 790958                     /lib/x86_64-linux-gnu/libpthread-2.15.so
7fd02699d000-7fd02699e000 r--p 00017000 08:01 790958                     /lib/x86_64-linux-gnu/libpthread-2.15.so
7fd02699e000-7fd02699f000 rw-p 00018000 08:01 790958                     /lib/x86_64-linux-gnu/libpthread-2.15.so
7fd02699f000-7fd0269a3000 rw-p 00000000 00:00 0 
7fd0269a3000-7fd0269c5000 r-xp 00000000 08:01 790858                     /lib/x86_64-linux-gnu/ld-2.15.so
7fd026bb0000-7fd026bb3000 rw-p 00000000 00:00 0 
7fd026bc1000-7fd026bc5000 rw-p 00000000 00:00 0 
7fd026bc5000-7fd026bc6000 r--p 00022000 08:01 790858                     /lib/x86_64-linux-gnu/ld-2.15.so
7fd026bc6000-7fd026bc8000 rw-p 00023000 08:01 790858                     /lib/x86_64-linux-gnu/ld-2.15.so
7ffff904b000-7ffff906c000 rw-p 00000000 00:00 0                          [stack]
7ffff91fe000-7ffff9200000 r-xp 00000000 00:00 0                          [vdso]
ffffffffff600000-ffffffffff601000 r-xp 00000000 00:00 0                  [vsyscall]

  • 메인 스레드에서 malloc한 후: 데이터 세그먼트 바로 위에 힙 세그먼트가 생성된 것을 볼 수 있다. 이것은 힙 메모리가 프로그램 브레이크 위치를 증가시킴으로써 생성된다는 것을 나타낸다. (예. brk 시스템 호출 사용) 또한 사용자가 1000 바이트를 요청했지만 132 킬로 바이트인 힙 메모리가 만들어졌음을 유의해야한다. 힙 메모리의 인접 영역을 Arena라고 한다. 메인 스레드에 생성된 ArenaMain Arena라고 한다. 추가 할당 요청으로 여유 공간이 부족해질 때 까지 이 Arena를 계속 사용한다. Arena 여유 공간이 부족한 경우, 프로그램 중단 위치를 늘려 확장시킨다.(증가하는 상위 덩어리의 크기가 추가 공간을 포함하도록 조정하여). 마찬가지로 상단 영역에 여유 공간이 많은 경우에 영역을 축소할 수 있다.
[Enter 입력]
After malloc and before free in main thread
$ cat /proc/2967/maps
00400000-00401000 r-xp 00000000 08:01 414686                             /home/osboxes/workspace/heap
00600000-00601000 r--p 00000000 08:01 414686                             /home/osboxes/workspace/heap
00601000-00602000 rw-p 00001000 08:01 414686                             /home/osboxes/workspace/heap
0091f000-00940000 rw-p 00000000 00:00 0                                  [heap]
7fd0263c6000-7fd02657b000 r-xp 00000000 08:01 790878                     /lib/x86_64-linux-gnu/libc-2.15.so
7fd02657b000-7fd02677b000 ---p 001b5000 08:01 790878                     /lib/x86_64-linux-gnu/libc-2.15.so
7fd02677b000-7fd02677f000 r--p 001b5000 08:01 790878                     /lib/x86_64-linux-gnu/libc-2.15.so
7fd02677f000-7fd026781000 rw-p 001b9000 08:01 790878                     /lib/x86_64-linux-gnu/libc-2.15.so
7fd026781000-7fd026786000 rw-p 00000000 00:00 0 
7fd026786000-7fd02679e000 r-xp 00000000 08:01 790958                     /lib/x86_64-linux-gnu/libpthread-2.15.so
7fd02679e000-7fd02699d000 ---p 00018000 08:01 790958                     /lib/x86_64-linux-gnu/libpthread-2.15.so
7fd02699d000-7fd02699e000 r--p 00017000 08:01 790958                     /lib/x86_64-linux-gnu/libpthread-2.15.so
7fd02699e000-7fd02699f000 rw-p 00018000 08:01 790958                     /lib/x86_64-linux-gnu/libpthread-2.15.so
7fd02699f000-7fd0269a3000 rw-p 00000000 00:00 0 
7fd0269a3000-7fd0269c5000 r-xp 00000000 08:01 790858                     /lib/x86_64-linux-gnu/ld-2.15.so
7fd026bb0000-7fd026bb3000 rw-p 00000000 00:00 0 
7fd026bc1000-7fd026bc5000 rw-p 00000000 00:00 0 
7fd026bc5000-7fd026bc6000 r--p 00022000 08:01 790858                     /lib/x86_64-linux-gnu/ld-2.15.so
7fd026bc6000-7fd026bc8000 rw-p 00023000 08:01 790858                     /lib/x86_64-linux-gnu/ld-2.15.so
7ffff904b000-7ffff906c000 rw-p 00000000 00:00 0                          [stack]
7ffff91fe000-7ffff9200000 r-xp 00000000 00:00 0                          [vdso]
ffffffffff600000-ffffffffff601000 r-xp 00000000 00:00 0                  [vsyscall]
  • 메인 스레드에서 free한 후: 할당 메모리 영역 해제 시 메모리가 운영체제에 의해 즉시 free되지 않는 것을 볼 수 있다. 할당된 메모리 영역은 glibc malloc라이브러리에서만 해제되며, 이 해제된 블록은 Main Arena bin에 추가된다. (glibc malloc에서 freelist 데이터 구조는 bin으로 참조된다.) 나중에 사용자가 메모리를 요청할 때, glibc malloc은 커널에서 새로운 힙 메모리를 얻는 대신 bin에서 빈 블록을 찾으려고 시도한다. 여유 블록이 없을 때만 커널에서 메모리를 확보한다.
[Enter 입력]
After free in main thread
$ cat /proc/2967/maps
00400000-00401000 r-xp 00000000 08:01 414686                             /home/osboxes/workspace/heap
00600000-00601000 r--p 00000000 08:01 414686                             /home/osboxes/workspace/heap
00601000-00602000 rw-p 00001000 08:01 414686                             /home/osboxes/workspace/heap
0091f000-00940000 rw-p 00000000 00:00 0                                  [heap]
7fd0263c6000-7fd02657b000 r-xp 00000000 08:01 790878                     /lib/x86_64-linux-gnu/libc-2.15.so
7fd02657b000-7fd02677b000 ---p 001b5000 08:01 790878                     /lib/x86_64-linux-gnu/libc-2.15.so
7fd02677b000-7fd02677f000 r--p 001b5000 08:01 790878                     /lib/x86_64-linux-gnu/libc-2.15.so
7fd02677f000-7fd026781000 rw-p 001b9000 08:01 790878                     /lib/x86_64-linux-gnu/libc-2.15.so
7fd026781000-7fd026786000 rw-p 00000000 00:00 0 
7fd026786000-7fd02679e000 r-xp 00000000 08:01 790958                     /lib/x86_64-linux-gnu/libpthread-2.15.so
7fd02679e000-7fd02699d000 ---p 00018000 08:01 790958                     /lib/x86_64-linux-gnu/libpthread-2.15.so
7fd02699d000-7fd02699e000 r--p 00017000 08:01 790958                     /lib/x86_64-linux-gnu/libpthread-2.15.so
7fd02699e000-7fd02699f000 rw-p 00018000 08:01 790958                     /lib/x86_64-linux-gnu/libpthread-2.15.so
7fd02699f000-7fd0269a3000 rw-p 00000000 00:00 0 
7fd0269a3000-7fd0269c5000 r-xp 00000000 08:01 790858                     /lib/x86_64-linux-gnu/ld-2.15.so
7fd026bb0000-7fd026bb3000 rw-p 00000000 00:00 0 
7fd026bc1000-7fd026bc5000 rw-p 00000000 00:00 0 
7fd026bc5000-7fd026bc6000 r--p 00022000 08:01 790858                     /lib/x86_64-linux-gnu/ld-2.15.so
7fd026bc6000-7fd026bc8000 rw-p 00023000 08:01 790858                     /lib/x86_64-linux-gnu/ld-2.15.so
7ffff904b000-7ffff906c000 rw-p 00000000 00:00 0                          [stack]
7ffff91fe000-7ffff9200000 r-xp 00000000 00:00 0                          [vdso]
ffffffffff600000-ffffffffff601000 r-xp 00000000 00:00 0                  [vsyscall]
  • 생성 스레드(thread 1)의 malloc 이전: thread 1의 힙 세그먼트는 아직 존재하지 않지만, 스택 영역이 생성된 것을 확인할 수 있다.
[Enter 입력]
Before malloc in thread 1
$ cat /proc/2967/maps
00400000-00401000 r-xp 00000000 08:01 414686                             /home/osboxes/workspace/heap
00600000-00601000 r--p 00000000 08:01 414686                             /home/osboxes/workspace/heap
00601000-00602000 rw-p 00001000 08:01 414686                             /home/osboxes/workspace/heap
0091f000-00940000 rw-p 00000000 00:00 0                                  [heap]
7fd025bc5000-7fd025bc6000 ---p 00000000 00:00 0 
7fd025bc6000-7fd0263c6000 rw-p 00000000 00:00 0                          [stack:2983]
7fd0263c6000-7fd02657b000 r-xp 00000000 08:01 790878                     /lib/x86_64-linux-gnu/libc-2.15.so
7fd02657b000-7fd02677b000 ---p 001b5000 08:01 790878                     /lib/x86_64-linux-gnu/libc-2.15.so
7fd02677b000-7fd02677f000 r--p 001b5000 08:01 790878                     /lib/x86_64-linux-gnu/libc-2.15.so
7fd02677f000-7fd026781000 rw-p 001b9000 08:01 790878                     /lib/x86_64-linux-gnu/libc-2.15.so
7fd026781000-7fd026786000 rw-p 00000000 00:00 0 
7fd026786000-7fd02679e000 r-xp 00000000 08:01 790958                     /lib/x86_64-linux-gnu/libpthread-2.15.so
7fd02679e000-7fd02699d000 ---p 00018000 08:01 790958                     /lib/x86_64-linux-gnu/libpthread-2.15.so
7fd02699d000-7fd02699e000 r--p 00017000 08:01 790958                     /lib/x86_64-linux-gnu/libpthread-2.15.so
7fd02699e000-7fd02699f000 rw-p 00018000 08:01 790958                     /lib/x86_64-linux-gnu/libpthread-2.15.so
7fd02699f000-7fd0269a3000 rw-p 00000000 00:00 0 
7fd0269a3000-7fd0269c5000 r-xp 00000000 08:01 790858                     /lib/x86_64-linux-gnu/ld-2.15.so
7fd026bb0000-7fd026bb3000 rw-p 00000000 00:00 0 
7fd026bc1000-7fd026bc5000 rw-p 00000000 00:00 0 
7fd026bc5000-7fd026bc6000 r--p 00022000 08:01 790858                     /lib/x86_64-linux-gnu/ld-2.15.so
7fd026bc6000-7fd026bc8000 rw-p 00023000 08:01 790858                     /lib/x86_64-linux-gnu/ld-2.15.so
7ffff904b000-7ffff906c000 rw-p 00000000 00:00 0                          [stack]
7ffff91fe000-7ffff9200000 r-xp 00000000 00:00 0                          [vdso]
ffffffffff600000-ffffffffff601000 r-xp 00000000 00:00 0                  [vsyscall]
  • 생성 스레드(thread 1)의 malloc: thread 1의 힙 세그먼트가 생성된 것을 볼 수 있다. 그리고 그 영역은 메모리 매핑 세크먼트 영역(7fd020000000-7fd020021000, 크기는 132KB)에 있으며, 따라서 힙 메모리는 메인 스레드(sbrk를 사용하는)와 달리 mmap 시스템 호출을 사용하여 생성되었음을 보여준다. 여기서도 사용자가 1000 바이트를 요청했지만 1 메가 바이트인 힙 메모리는 프로세스 주소 공간에 매핑된다. 이 1 메가 바이트 중 132 킬로 바이트의 읽기, 쓰기 권한만 설정되며 이 스레드의 힙 메모리가 된다. 이 인접한 메모리 영역(132KB)을 스레드 영역이라고 한다.

참고 : 사용자 요청 크기가 128KB를 초과하면 (malloc (132 * 1024)라고 말하게 함) 사용자 요청을 충족하기에 충분한 공간이 공간에 없을 때 mmap syscall을 사용하여 (sbrk를 사용하지 않고) 할당된다.

[Enter 입력]
After malloc and before free in thread 1
$ cat /proc/2967/maps
00400000-00401000 r-xp 00000000 08:01 414686                             /home/osboxes/workspace/heap
00600000-00601000 r--p 00000000 08:01 414686                             /home/osboxes/workspace/heap
00601000-00602000 rw-p 00001000 08:01 414686                             /home/osboxes/workspace/heap
0091f000-00940000 rw-p 00000000 00:00 0                                  [heap]
7fd020000000-7fd020021000 rw-p 00000000 00:00 0 
7fd020021000-7fd024000000 ---p 00000000 00:00 0 
7fd025bc5000-7fd025bc6000 ---p 00000000 00:00 0 
7fd025bc6000-7fd0263c6000 rw-p 00000000 00:00 0                          [stack:2983]
7fd0263c6000-7fd02657b000 r-xp 00000000 08:01 790878                     /lib/x86_64-linux-gnu/libc-2.15.so
7fd02657b000-7fd02677b000 ---p 001b5000 08:01 790878                     /lib/x86_64-linux-gnu/libc-2.15.so
7fd02677b000-7fd02677f000 r--p 001b5000 08:01 790878                     /lib/x86_64-linux-gnu/libc-2.15.so
7fd02677f000-7fd026781000 rw-p 001b9000 08:01 790878                     /lib/x86_64-linux-gnu/libc-2.15.so
7fd026781000-7fd026786000 rw-p 00000000 00:00 0 
7fd026786000-7fd02679e000 r-xp 00000000 08:01 790958                     /lib/x86_64-linux-gnu/libpthread-2.15.so
7fd02679e000-7fd02699d000 ---p 00018000 08:01 790958                     /lib/x86_64-linux-gnu/libpthread-2.15.so
7fd02699d000-7fd02699e000 r--p 00017000 08:01 790958                     /lib/x86_64-linux-gnu/libpthread-2.15.so
7fd02699e000-7fd02699f000 rw-p 00018000 08:01 790958                     /lib/x86_64-linux-gnu/libpthread-2.15.so
7fd02699f000-7fd0269a3000 rw-p 00000000 00:00 0 
7fd0269a3000-7fd0269c5000 r-xp 00000000 08:01 790858                     /lib/x86_64-linux-gnu/ld-2.15.so
7fd026bb0000-7fd026bb3000 rw-p 00000000 00:00 0 
7fd026bc1000-7fd026bc5000 rw-p 00000000 00:00 0 
7fd026bc5000-7fd026bc6000 r--p 00022000 08:01 790858                     /lib/x86_64-linux-gnu/ld-2.15.so
7fd026bc6000-7fd026bc8000 rw-p 00023000 08:01 790858                     /lib/x86_64-linux-gnu/ld-2.15.so
7ffff904b000-7ffff906c000 rw-p 00000000 00:00 0                          [stack]
7ffff91fe000-7ffff9200000 r-xp 00000000 00:00 0                          [vdso]
ffffffffff600000-ffffffffff601000 r-xp 00000000 00:00 0                  [vsyscall]
  • 생성 스레드(thread 1)의 free: 할당된 메모리 영역을 해제해도 운영체제에 힙 메모리가 제거되지 않는다는 것을 알 수 있다. 대신 할당된 메모리 영역(1000 바이트 크기)이 glibc malloc에 해제되고, 이 해제된 블록이 스레드 영역 저장소에 추가된다.
[Enter 입력]
After free in thread 1
$ cat /proc/2967/maps
00400000-00401000 r-xp 00000000 08:01 414686                             /home/osboxes/workspace/heap
00600000-00601000 r--p 00000000 08:01 414686                             /home/osboxes/workspace/heap
00601000-00602000 rw-p 00001000 08:01 414686                             /home/osboxes/workspace/heap
0091f000-00940000 rw-p 00000000 00:00 0                                  [heap]
7fd020000000-7fd020021000 rw-p 00000000 00:00 0 
7fd020021000-7fd024000000 ---p 00000000 00:00 0 
7fd025bc5000-7fd025bc6000 ---p 00000000 00:00 0 
7fd025bc6000-7fd0263c6000 rw-p 00000000 00:00 0                          [stack:2983]
7fd0263c6000-7fd02657b000 r-xp 00000000 08:01 790878                     /lib/x86_64-linux-gnu/libc-2.15.so
7fd02657b000-7fd02677b000 ---p 001b5000 08:01 790878                     /lib/x86_64-linux-gnu/libc-2.15.so
7fd02677b000-7fd02677f000 r--p 001b5000 08:01 790878                     /lib/x86_64-linux-gnu/libc-2.15.so
7fd02677f000-7fd026781000 rw-p 001b9000 08:01 790878                     /lib/x86_64-linux-gnu/libc-2.15.so
7fd026781000-7fd026786000 rw-p 00000000 00:00 0 
7fd026786000-7fd02679e000 r-xp 00000000 08:01 790958                     /lib/x86_64-linux-gnu/libpthread-2.15.so
7fd02679e000-7fd02699d000 ---p 00018000 08:01 790958                     /lib/x86_64-linux-gnu/libpthread-2.15.so
7fd02699d000-7fd02699e000 r--p 00017000 08:01 790958                     /lib/x86_64-linux-gnu/libpthread-2.15.so
7fd02699e000-7fd02699f000 rw-p 00018000 08:01 790958                     /lib/x86_64-linux-gnu/libpthread-2.15.so
7fd02699f000-7fd0269a3000 rw-p 00000000 00:00 0 
7fd0269a3000-7fd0269c5000 r-xp 00000000 08:01 790858                     /lib/x86_64-linux-gnu/ld-2.15.so
7fd026bb0000-7fd026bb3000 rw-p 00000000 00:00 0 
7fd026bc1000-7fd026bc5000 rw-p 00000000 00:00 0 
7fd026bc5000-7fd026bc6000 r--p 00022000 08:01 790858                     /lib/x86_64-linux-gnu/ld-2.15.so
7fd026bc6000-7fd026bc8000 rw-p 00023000 08:01 790858                     /lib/x86_64-linux-gnu/ld-2.15.so
7ffff904b000-7ffff906c000 rw-p 00000000 00:00 0                          [stack]
7ffff91fe000-7ffff9200000 r-xp 00000000 00:00 0                          [vdso]
ffffffffff600000-ffffffffff601000 r-xp 00000000 00:00 0                  [vsyscall]

Arena

아레나의 수

아레나의 수: 위 예제에서 메인 스레드는 메인 아레나를 포함하고 thread 1은 자체 스레드 아레나를 포함한다. 잘못 설계된 프로그램은 코어 수보다 많은 수의 스레드를 포함할 수 있으나, 이 경우 스레드 당 하나의 아레나를 대응시키는 것은 비효율적인 일이 되므로 응용 프로그램의 영역 제한은 시스템에 있는 코어 수를 기반으로 한다.

  • 32 bit 시스템: 아레나 수 = 2 * 코어 수.
  • 64 bit 시스템: 아레나 수 = 8 * 코어 수.

다중 아레나

다중 아레나: 멀티 스레드 응용 프로그램(4개의 스레드 - 메인 스레드 + 3개의 사용자 스레드)이 1개의 코어를 포함하는 32 비트 시스템에서 실행될 때, 스레드 수(4) > 2 * 코어 수(2)로 가정하면 glibc malloc은 여러 개의 영역이 사용 가능한 모든 스레드에서 공유되도록 한다. 어떻게 공유할 수 있을까?

  • 메인 쓰레드가 malloc을 처음 호출 할 때 이미 생성 된 메인 아레나는 아무런 충돌없이 사용된다.

  • 스레드 1과 스레드 2가 malloc을 처음 호출 할 때, 새로운 아레나가 만들어지고 그것들은 경쟁없이 사용된다. 이 시점까지 스레드와 아레나는 일대일 매핑을 가진다.

  • 스레드 3이 malloc을 처음 호출하면 아레나 한도가 계산된다. 여기에 아레나 한도를 넘기 때문에 기존 아레나 (메인 아레나 또는 아레나 1 또는 아레나 2)을 재사용한다.

  • 재사용 :

    • 사용 가능한 아레나들이 한 번의 루프를 넘는 동안, 아레나에 lock을 반복한다.
    • 성공적으로 lock된 경우 (메인 아레나가 성공적으로 lock된 경우) 해당 아레나를 사용자에게 반환 한다.
    • 만약 어떠한 아레나도 해제되지 않은 경우, 다음 행에 아레나를 위한 블럭이 있다.
  • 이제 스레드 3이 malloc (두 번째 시간)을 호출하면 malloc은 마지막 액세스 된 아레나 (메인 아레나) 를 사용하려고 시도한다 . 메인 아레나가 사용 가능하지 않은 경우, 메인 아레나가 해제 될 때까지 thread3가 차단된다. 따라서 메인 아레나는 메인 쓰레드와 쓰레드 3 사이에서 공유된다.

다중 힙

다중 힙: 주로 glibc malloc의 소스 코드에서 아래와 같은 3개의 데이터 구조체를 확인할 수 있다.

  • heap_info: Heap Header - 단일 스레드 아레나는 여러 개의 힙을 가질 수 있다. 각 힙은 각자의 헤더를 가진다. 왜 여러 개의 힙이 필요한가? 모든 스레드 아레나는 오직 하나의 힙만을 가지고 시작하지만, 힙 영역의 공간이 부족해지는 경우, 아레나에 새로운 힙(인접하지 않은 영역)을 할당해주어야 한다.
  • malloc_state: Arena Header - 단일 스레드 아레나는 여러 개의 힙을 가질 수 있지만, 이러한 모든 힙에 대한 오직 하나의 아레나 헤더만이 존재한다. 아레나 헤더는 bin, top chunk, last remainder chunk등에 대한 정보를 가진다.
  • malloc_chunk: Chunk Header - 힙은 사용자 요청을 토대로 많은 청크로 분열된다. 그리고 각각의 청크는 청크 헤더를 가진다.
  • 메인 아레나는 여러 개의 힙과 heap_info 구조체를 가질 수 없다. 메인 아레나의 공간이 부족한 경우, sbrk 힙 영역은 메모리가 매핑된 영역까지 확장(인접한 영역)된다.
  • 스레드 아레나와 달리 메인 아레나의 아레나 헤더는 sbrk 힙 영역의 일부가 아니다. 메인 아레나는 전역 변수이며, libc.so의 데이터 영역에서 찾을 수 있다.

메인 아레나와 스레드 아레나를 그림으로 나타낸 경우 (단일 힙 영역):
enter image description here

스레드 아레나를 그림으로 나타낸 경우 (여러 개의 힙 영역):
enter image description here

Chunk

청크: 청크는 힙 영역에서 찾을 수 있으며, 아래의 타입 중 하나를 가진다.

  • Allocated chunk
  • Free chunk
  • Top chunk
  • Last Remainder chunk

Allocated chunk

enter image description here

  • prev_size: 이전 청크가 비어 있다면 이전 청크의 크기를 저장하고 이전 청크가 할당된 경우에는 이전 청크의 사용자 데이터를 저장한다.
  • size: 할당된 청크의 크기를 포함한다. 이 필드의 마지막 3 비트는 플래그 정보를 포함한다.
    • PREV_INUSE § - 이전 청크가 할당될 때 설정
    • IS_MMAPPED (M) - 청크가 mmap될 때 설정
    • NON_MAIN_ARENA (N) - 청크가 스레드 아레나에 속할 때 설정

malloc_chunk(fd, bk와 같은)의 다른 필드는 할당된 청크에 사용되지 않는다. 따라서 이 필드 대신 사용자 데이터가 저장된다.
사용자가 요청한 크기는 malloc_chunk 저장하고 메모리를 정렬하기 위해서는 약간의 공간이 여분으로 필요하기 때문에 사용할 수 있는 크기(청크 내부를 나타내는 크기)로 변환된다.

Free chunk

enter image description here

  • prev_size: 2개의 free chunk는 서로 인접할 수 없다. 두 청크가 모두 비어 있다면 하나의 단일 청크로 결합된다. 따라서 항상 해제된 청크의 이전 청크를 할당하고 있어서, prev_size는 이전 청크의 사용자 데이터를 저장하고 있다.
  • size: free chunk의 크기를 저장하고 있다.
  • fd: Forward pointer - 동일한 빈에서의 다음 청크를 가리킨다. (물리 메모리에서의 다음 청크가 아님)
  • bk: Backward pointer - 동일한 빈에서의 이전 청크를 가리킨다. (물리 메모리에서의 이전 청크가 아님)

Bins

Bins: Bin은 freelist data structures이며, free chunk들을 수용하는 데 사용한다. 청크의 크기를 기준으로 사용 가능한 bin이 달라진다.

  • Fast bin
  • Unsorted bin
  • Small bin
  • Large bin

이러한 빈들을 저장하는 데, 다음의 데이터 구조를 사용한다.

  • fastbinsY: 이 배열은 fast bin을 수용한다.
  • bins: 이 배열은 정렬되지 않은 크고 작은 빈을 저장한다. 총 126개의 bin이 있고 다음과 같은 기준으로 나뉜다.
    • Bin 1 - Unsorted bin
    • Bin 2 ~ Bin 63 - Small bin
    • Bin 64 ~ Bin 126 - Large bin
Fast Bin

Fast Bin: 청크의 크기가 16 ~ 80바이트인 경우, fast chunk라고 부른다. fast chunk를 수용한 bin을 fast bin이라고 부른다. 모든 bin들 중 가운데, fast bin은 메모리 할당과 반납(해제)가 빠르다.

  • bin의 갯수 - 10
    • 각 fast bin은 free chunk로 구성된 단일 연결리스트(다른 말로 binlist)를 가진다. 단일 연결리스트는 list의 중간으로부터 fast bin chunk을 제거할 수 없기 때문에 사용된다. 추가와 제거는 list의 앞쪽 끝에서 발생한다 - LIFO.
  • 청크의 크기 - 각 8바이트씩
    • Fast bin은 각 8바이트 크기를 가지는 청크의 binlist를 가진다. 예) 첫 번째 fast bin(index 0)은 16바이트 크기의 청크 binlist를 가지며, 두 번째 fast bin(index 1)은 24바이트 크기의 청크 binlist를 가지는 식으로, 이어진다.
    • fast bin 내부의 청크는 동일한 크기이다.
  • malloc 초기화에서, fast bin의 최대 크기는 64(!80)바이트로 세트되어 있다. 따라서, 기본 청크의 크기는 16 ~ 64인 경우, fast chunk로 분류된다.
  • 병합 없음 - 해제된 2개의 청크가 서로 인접해 있을 수 있으며, 단일 free chunk로 결합되지 않는다. 병합이 없다는 것은 외부 단편화라는 결과를 가져올 수 있지만 해제의 속도가 빠르다는 장점이 있다.
  • malloc(fast chunk) -
    • 초기의 fast bin의 최대 크기와 fast bin 인덱스는 비어 있기 때문에, 사용자가 fast chunk를 요청하더라도, fast bin code 대신, small bin code가 서비스할 수 있다.
    • 이후에 비어있지 않게 된 경우, fast bin 인덱스는 해당하는 binlist로부터 검색을 하여 계산된다.
    • 위에서 반환된 binlist의 첫 번째 청크는 삭제된 후, 사용자에게 반환된다.
  • free(fast chunk) -
    • Fast bin 인덱스는 해당하는 binlist로부터 검색을 하여 계산된다.
    • free chunk는 위에서 반환된 binlist의 앞쪽 위치에 추가된다.

enter image description here

Unsorted Bin

Unsorted Bin: small 또는 large chunk가 각각의 빈에 추가되지 않고 해제되면 Unsorted bin에 저장된다. 이 방법은 glibc malloc에게 최근에 해제된 청크를 재사용할 수 있는 두 번째 기회를 제공한다. 따라서 적절한 bin을 찾는 데 걸리는 시간이 없으므로 메모리 할당 및 할당 해제 속도가 빨라진다. (unsorted bin이기 때문에)

  • bin의 개수 - 1
    • Unsorted bin은 free chunk의 환형 이중 연결 리스트(다른 말로 binlist)를 가진다.
  • 청크의 크기 - 크기에 제한이 없기 때문에 다양한 크기의 청크가 bin에 저장될 수 있다.

enter image description here

Small Bin

Small Bin: 청크 크기가 512 바이트보다 작은 경우, Small chunk라고 부르며, Small chunk가 저장된 Bin을 Small Bin이라 한다. Small Bin은 메모리 할당 및 반환이 Large Bin보다 빠르다. (Fast Bin보다는 느리다)

  • bin의 개수 - 62
    • 각 Small Bin은 Free chunk로 구성된 환형 이중 연결리스트를 가진다. 이중 연결리스트는 list의 중간에서 small bin chunk를 제거할 수 있기 때문에 사용된다. 노드의 추가는 앞쪽 끝에서 발생하고 삭제는 list의 뒤쪽 끝에서 발생한다 - FIFO.
  • 청크의 크기 - 각 8바이트씩
    • Small Bin은 각 8바이트 크기를 가지는 청크 binlist를 가진다. 예) 첫 번째 Small bin(Bin 2)은 16바이트 크기의 청크 binlist를 가지며, 두 번째 small bin(Bin 3)은 24바이트 크기의 청크 binlist를 가지는 식으로, 이어진다.
    • Small Bin 내부의 청크는 동일한 크기이며, 따라서 정렬이 필요없다.
  • 병합 - 해제된 2개의 청크는 각각 인접해 있을 수 없으며, 단일 Free chunk로 결합된다. 병합은 외부 단편화를 제거하지만, 해제의 속도가 느리다.
  • malloc(small chunk) -
    • 초기의 모든 Small Bin은 NULL이기 때문에, 사용자가 Small chunk를 요청했더라도, Small Bin code 대신, Unsorted Bin code가 서비스할 수 있다.
    • 또한 malloc을 처음 호출할 경우, malloc_state에 있는 Small Bin과 Large Bin의 데이터 구조(bins)가 초기화된다. 즉, bin은 비어있는 자기자신을 가리키고 있다.
    • 나중에 Small Bin이 비어있지 않으면, 해당 binlist의 마지막 청크가 제거된 후, 사용자에게 반환된다.
  • free(small chunk) -
    • 이 청크를 해제하는 동안, 이전 또는 다음 청크가 해제되었는지 체크하여, 해제된 경우 병합한다. 예) 각각의 연결 리스트로부터 청크를 제거하고 unsorted bin의 연결 리스트의 시작 부분에 새롭게 합병된 청크를 추가한다.
Large Bin

Large Bin: 청크 크기가 512 바이트보다 크거나 같은 경우 Large chunk라고 부르며, Large chunk가 저장된 Bin을 Large Bin이라고 한다. Large Bin은 메모리 할당과 반환이 Small Bin보다 느리다.

  • bin의 개수 - 63
    • 각 Large Bin은 Free chunk로 구성된 환형 이중 연결리스트를 가진다. 이중 연결리스트는 어느 위치(맨 앞, 중간, 끝)에서나 Large Bins chunk를 추가하고 삭제할 수 있기 때문에 사용된다.
    • 63개의 bins :
      • 32개의 bin은 각 64바이트 크기를 가지는 청크의 binlist를 가진다. 예) 첫 번째 large bin(Bin 65)은 512바이트 ~ 568바이트 크기의 청크 binlist를 가지고, 두 번째 large bin(Bin 66)은 576바이트 ~ 632바이트 크기의 청크 binlist를 가지는 식으로, 이어진다.
      • 16개의 bin은 각 512바이트 크기를 가지는 청크의 binlist를 가진다.
      • 8개의 bin은 각 4,096바이트 크기를 가지는 청크의 binlist를 가진다.
      • 4개의 bin은 각 32,768바이트 크기를 가지는 청크의 binlist를 가진다.
      • 2개의 bin은 각 262,144바이트 크기를 가지는 청크의 binlist를 가진다.
      • 1개의 bin은 남은 크기를 가지는 청크를 가진다.
    • Small Bin과 달리, Large Bin 내부의 청크는 동일한 크기를 가지고 있지 않다. 따라서, 내림차순으로 저장된다. 가장 큰 청크는 binlist의 가장 앞쪽에 저장되고, 가장 작은 청크는 binlist의 가장 뒷쪽에 저장된다.
  • 병합 - 해제된 2개의 청크는 각각 인접해 있을 수 없으며, 단일 Free chunk로 결합된다.
  • malloc(large chunk) -
    • 초기의 모든 Large Bin은 NULL이기 때문에, 사용자가 Large chunk를 요청했더라도, Large Bin code 대신, Next Largest Bin code가 서비스할 수 있다.
    • 또한 malloc을 처음 호출할 경우, malloc_state에 있는 Small Bin과 Large Bin의 데이터 구조(bins)가 초기화된다. 즉, bin은 비어있는 자기자신을 가리키고 있다.
    • 이후에 Large Bin이 비어있지 않은 경우에서, 가장 큰 청크(해당 binlist에서)의 크기가 사용자가 요청한 크기보다 크다면, binlist를 뒷쪽 끝부터 앞쪽 끝까지 확인하여, 사용자가 요청한 크기에 가깝거나 같은 적합한 크기의 청크를 찾는다. 찾게 되면, 해당 청크는 2개의 청크로 분리된다.
      • User chunk(사용자가 요청한 크기) - 사용자에게 반환
      • Remainder chunk(나머지 크기) - Unsorted bin에 추가
    • 만일 가장 큰 청크(이것의 binlist에서)의 크기가 사용자가 요청한 크기보다 작다면, 비어있지 않는 다음 Largest Bin을 사용하여 사용자의 요청에 응답한다. 다음 Largest Bin code는 비어있지 않은 다음 Largest Bin을 찾기 위해 binmaps을 스캔하여, 해당하는 bin을 찾은 경우, 해당 binlist에서 적합한 청크가 검색되고, 적합한 청크를 분리하여 사용자에게 반환된다. 만일 찾지 못 한 경우에는, Top chunk를 사용하여 사용자의 요청에 응답한다.
  • free(large chunk) - free(small chunk)와 절차가 비슷하다.

Top chunk

Top chunk: 아레나 최상단 경계에 위치한 청크를 Top chunk 라고 한다. Top chunk는 어떤 bin에도 속하지 않고 bin에 블록이 없을 때 사용자 요청을 처리하는 데 사용된다. Top chunk 크기가 사용자 요청 크기보다 큰 경우 상위 청크가 두개로 분할된다.

  • User chunk (사용자 요청 크기)
  • Remainder chunk (나머지 크기)

Remainder chunk는 새로운 꼭대기가 된다. 만일 Top chunk의 크기가 사용자가 요청한 크기보다 작은 경우, sbrk(메인 아레나) 또는 mmap(스레드 아레나) 시스템 호출을 사용하여 Top chunk를 확장시킨다.

Last Remainder chunk

Last Remainder chunk: 가장 최근의 작은 요청 분할로 부터 남은 크기. Last Remainder chunk는 지역 참조성을 증가시키는 데 도움이 된다. 즉, 작은 덩어리에 대한 malloc 요청이 연속적으로 서로 가까이 할당 될 수 있다.

그러나 아레나에서 사용할 수 있는 많은 청크 중 Last Remainder chunk에 적합한 청크는 무엇인가?

작은 청크에 대한 사용자 요청이 Small bin 및 Unsorted bin에 의해 제공 될 수 없으면 binmaps가 스캔되어 다음으로 큰 bin (비어 있지 않은) 을 찾는다. 앞서 말했듯이, 다음으로 큰 bin (비어 있지 않은)을 찾은 다음, 2로 나누면 사용자 청크가 사용자에게 반환되고 나머지 청크는 unsorted bin에 추가된다. 이 추가로 새로운 Last Remainder chunk가 발생된다.

참조 지역이 어떻게 달성 되는가?

이제 사용자가 작은 청크를 요청하고 Last Remainder chunk가 Unsorted bin의 유일한 청크 인 경우 Last Remainder chunk가 두 개로 분할 되고 User chunk가 사용자에게 반환되고 Remainder chunk는 Unsorted bin에 추가된다. 이 추가롤 새로운 Last Remainder chunk가 발생된다. 따라서 후속 메모리 할당은 결국 서로 인접하게 된다.

이 블로그의 인기 게시물

X-Frame-Options-Test

X-Frame-Options 테스트하기 X-Frame-Options 페이지 구성 시 삽입된 프레임의 출처를 검증하여 허용하지 않는 페이지 URL일 경우 해당 프레임을 포함하지 않는 확장 응답 헤더이다. 보안 목적으로 사용되는 확장 헤더로 아직 적용되지 않은 사이트들이 많지만 앞으로 점차 적용될 것으로 보인다. X-Frame OptionsDENY, SAMEORIGIN, ALLOW-FROM 옵션을 이용하여 세부 정책을 설정한다. 옵션 설명 DENY Frame 비허용 SAMEORIGIN 동일한 ORIGIN에 해당하는 Frame만 허용 ALLOW-FROM 지정된 ORIGIN에 해당하는 Frame만 허용 크롬 4.1 , IE 8 , 오페라 10.5 , 사파리 4.0 , 파이어폭스 3.6.9 이상에서는 DENY , SAMEORIGIN 이 적용되며, ALLOW-FROM 은 각 브라우저 마다 지원 현황이 다르다. https://developer.mozilla.org/ko/docs/Web/HTTP/Headers/X-Frame-Options 해당 확장헤더는 브라우저에서 처리하는 응답 헤더이므로 미지원 브라우저 사용 시 설정과 무관하게 페이지 내 포함된 모든 Frame을 출력한다. (검증 테스트: Opera 5.0.0) 테스트 코드 DENY <!DOCTYPE html> < html lang = "en" > < head > < meta http-equiv = "X-Frame-Options" content = "deny" /> < title > Deny option Test </ title > </ head > < bod

C-lang-vulnerabilities

C 언어 공통 취약점 해당 글은 CERN Computer Security의 Common vulnerabilities guide for C programmers 글을 참고하여 작성하였습니다. C언어에서 발생하는 대부분의 취약점은 버퍼 오버플로우와 문자열 처리 미흡과 관련되어 있다. 이는 segmentation fault를 유발하고 입력 값을 조작할 경우 임의 코드 실행으로 이어질 수 있다. 이에 대부분의 에러와 조치 방안을 살펴보자고 한다. gets stdio gets() 함수는 버퍼 길이를 검증하지 않아 사용 시 항상 취약성을 야기한다. Vulnerable Code #include<stdio.h> int main() { char username[ 8 ]; int allow = 0 ; printf ( "Enter your username, please: " ); gets(username); //악의적인 값 삽입 if (grantAccess(username)) { allow = 1 ; } if (allow != 0 ) { //username을 오버플로우하여 덮어씀 privilegeAction(); } return 0 ; } Mitigation fgets() 함수 사용 및 동적 메모리 할당 #include <stdio.h> #include <stdlib.h> #define LENGTH 8 int main () { char * username, *nlptr; int allow = 0 ; username = malloc (LENGTH * sizeof (*username)); if (!username) return EXIT_FAILURE; printf ( "Enter your username, please:

HTML/CSS를 활용하여 카카오톡 클론 만들기

시간을 내어 HTML과 CSS를 공부한 것은 대학생 때가 마지막이었던 것으로 기억한다. 그 동안 사이드 프로젝트로 진행했던 여러 아이디어들을 결국 서비스하지 못했던 결정적인 이유는 프론트 엔드 기술 부족이었다고 생각하고 우선 HTML과 CSS 학습을 진행하였다. 프론트 엔드 기술은 많은 발전을 거듭하여 예전에 비해 큰 복잡성을 가지게 되었다. 빠른 시간 안에 숙지하지 못한 기법들에 대해서 알아보고 구현하고자 하는 아이디어에 활용할 수 있을 정도로 진행해보고자 한다. 또한 보안적 관점에서 발생할 수 있는 프론트 엔드 위협에 대해 파악할 수 있는 좋은 밑거름이 되길 기대해본다. 우선적으로 진행한 카카오 톡 디자인 클론은 노마드 아카데미의 강의를 수강하며 진행하였고 결과는 아래의 링크에서 확인할 수 있다. 소스코드 저장소 구현된 웹 페이지