malloc 의 이해
동적할당 : C 언어에서 runtime 시에 새로운 메모리를 사용해야 하는 경우에 프로그램 실행중에 메모리 를 할당하는 것 동적할당의 필요성 : 컴파일시에 소스에서 선언된 변수는 스택영역에서 한번에 메모리를 할당한 후 프 로그램이 동작하기 때문에 runtime시에 할당하려는 메모리는 동적할당을 통해서 할수 있다.
동적할당을 하기 위한 C 에서 사용하는 함수 malloc()이다. malloc() 의 인자는 요청할 공간의 크기, 반환 값은 공간의 주소이다.
malloc()을 더 깊게 공부하고 싶다면 malloc.c를 분석해보는 것을 추천한다.
ptmalloc2
동적할당을 통해서 메모리가 제공되는 공간은 Heap 영역이다.
위와 같은 사진에서 알수 있듯이, 프로그램 실행시 메모리는 크게 4개의 영역으로 나뉘어 지는데, 이제까지는 스택을 통한 오버플로우만을 공부해왔다. 힙영역은 스택과는 달리 Runtime시에 할당되는 영역이기 때문에, 스택보다 동적이고 관리가 복잡 하다. 따라서, 우리는 힙에서 메모리가 처리되는 과정을 자세히 다룰 필요가 있다. 메모리 할당자(Memory Allocater)는 이러한 힙영역을 할당하고 해제하고 관리하는 알고리즘이다. 그 중 우리는 해킹공부를 하면서 가장 많이 접하게 될 linux에서의 ptmalloc2에 대해 다루어 보자.
청크(Chunk)
힙영역은 기본적으로 메모리를 할당할 때, 청크(Chunk) 단위로 할당을 하게 된다. 청크의 구조가 어떻게 생겼는지 알아볼 필요가 있다.
struct malloc_chunk {
INTERNAL_SIZE_T prev size;
INTERNAL_SIZE_T size;
struct malloc_chunk* fd;
struct malloc_chunk* bk;
struct malloc_chunk* fd_nextsize;
struct malloc_chunk* bk_nextsize;
};
이런 식으로 표현 된다. 위에 있는 prev_size와 size라고 표현한 부분은 Header라고 부르는 영역이다. Chunk의 크기에 대한 정보를 담고 있고 64bit 기준으로 크기는 0x10byte이다. size는 요청한 크기 + header의 크기이다. 하위 3bit는 flag로 사용되기 때문에 보통 malloc(0x30)을 했다면 0x40이라고 적혀있어야 정상적인 것처럼 보이지만 실제로 보면 0x41정도로 적혀있다. prev_size는 이전 청크의 size로 이전 청크가 해제되어야 세팅된다. 그 아래에 있는 user data라는 영역이 실직적으로 사용자가 malloc()을 통해 사용하는 공간이다. 그리고 int* a = malloc(0x30) 이런 식으로 a에 청크의 주소를 담았을때 a에 들어가는 값은 header 의 시작주소가 아니라 user data의 시작주소이다.
x64 heap align : 0x10 byte
청크는 0x10바이트 단위로 할당된다는 뜻이다. 예를들어 malloc(0x38)을 하면 malloc(0x30)을 하고 다음 청크의 prev_size까지 쓰는 방식으로 되 고, malloc(0x39)를 하면 molloc(0x40)으로 한 것과 같은 반응을 보이고, 다음 청크의 영역은 사용하지 않는다. x64 minimum size : 0x20 byte
struct malloc_chunk { INTERNAL_SIZE_T prev size; INTERNAL_SIZE_T size; struct malloc_chunk* fd; struct malloc_chunk* bk; struct malloc_chunk* fd_nextsize; struct malloc_chunk* bk_nextsize; };
그에 따라 malloc(0x1)을 하더라도 malloc(0x10)을 한 것과 같이 되기 때문에, userdata에다가 header의 크기까지 계산하면 청크의 최소 크기는 0x20 byte가 된다. 또한 할당 요청마다 아래로 청크를 쌓아가서, 할당 순서대로 점점 청크의 주소는 커지면서 연속적이다.
Top Chunk
그렇다면 어디에서 메모리를 가져와서 쓰는 것일까? Heap 할당 요청이 처음으로 들어오면 ptmalloc2 : sysmalloc() -> memory allocation syscall main thread : sys_mmap child thread : sys_sbrk 그 후 Top Chunk라는 큰 청크를 생성하여 이후에 요청을 받으면 Top Chunk에서 공간을 떼어준다.
free란 무엇인가?
동적할당을 통해서 heap 영역에 대한 memory를 사용할 수 있다는 것을 학습하였다. 만약 할당한 공간을 더 이상 사용하지 않게 된다면 어떻게 해야할까? 그 답은 바로 사용하지 않는 공간을 해제하는 것이다. 공간을 해제 한 후 새로운 공간을 할당할 때, 새로운 청크를 새로운 영역에다가 만드는 것이 아니 라, 해제 했던 영역을 재사용하는 방식으로 우리는 memory를 절약할 수 있다. 이때 memory leak(메모리 누수)는 사용하지 않는 공간을 해제하지 않아서, 불필요한 공간을 계속 차지한 상태에서 새로운 공간을 계속해서 할당해 나가는 것이다. 공간을 해제하는 방법은 free()함수를 이용하는 것이다. 함수의 인자로 공간은 주소를 넘겨주어 해당 영역의 공간을 할당해제할 수 있다.
bin
free()를 통해서 heap공간을 차지하고 있는 메모리를 해제했다면, 해제된 힙은 어디서 관리되는 것 일까?
arena
Thread가 단일 Thread라는 가정하에 지금 부터 이야기를 시작하겠다. 단일Thread에서는 하나뿐인 arena main arena가 존재한다. arena 에서는 'bin'으로 해제된 chunk를 관리한다. bin은 해제된 chunk들의 리스트로 chunk가 해제될 시 bin에 등록되는 방식으로 관리가 이루어진 다. bin의 구조는 크게 2개로 나뉘어진다. singly-linked list의 구조를 가진 bin과 doubly-linked list의 구조를 가진 bin이 있다. singly-linked list는 사용자가 사용하는 데이터 영역외에, 링크영역을 두어 먼저 들어온 데이터의 주소를 담고 있는 구조이다. doubly-linked list는 사용자가 사용하는 데이터 영역외에, 링크영역을 두어 먼저들어온 데이터의 주소 뿐만 아니라 바로 다음에 들어오는 데이터의 주소까지도 담고있는 구조이다. 해제된 chunk는 fd, bk 를 두어 이러한 list를 형성한다.
fd 는 foward의 약어로 앞 청크의 주소이다. 포인터의 개념으로 앞청크를 가르킨다고도 표현한다.
bk 는 backward의 약어로 뒷 청크의 주소이다. 포인터의 개념으로 뒷청크를 가르킨다고도 표현한다.
bin은 크게 4종류로 나뉘어진다.
bin을 분류하는 기준은 해제된 청크의 사이즈 이다.
fastbin : size <= 0x80 // singly-linked list
small bin : size < 0x200 // circular doubly-linked list
large bin : 나머지 // circular doubly-linked list
unsorted bin : 분류되지 않은 bin으로, small bin 이상의 사이즈가 해제되면 일단 unsorted bin 에 등록이 된다. 추후, 새 메모리를 할당 할 때, 할당받길 원하는 크기 이상의 청크가 unsorted bin 에 등록이 되어있다면, 바로 반환을 해주고 unsorted bin을 모두 돌아봤지만, 반환해 줄 청크가 없다면, 그때, unsorted bin에 등록되어있던 청크들을 사이즈에 맞게 small bin과 large bin으로 보낸다.
// circular doubly-linked list
fastbin -> LIFO 방식
fastbin 은 LIFO 방식이다. LIFO는 Last In First Out으로 Stack 처럼, 가장 나중에 들어온 것이 먼저 나간다는 뜻이다.
unsorted bin -> FIFO 방식
unsorted bin은 FIFO 방식이다. FIFO는 First In First Out으로 먼저들어온 것이 먼저 나간다는 뜻이다.
Unlink
bin에서 chunk가 빠지거나 다른 bin으로 이동을 할 때, 수행하는 동작이다. unlink의 동작은 다음과 같다.
#define unlink(P, BK, FD){
BK = P -> bk;
FD = P -> fd;
FD -> bk = BK;
BK -> fd = FD;
}
arena & bin
arena에서는 'bin'으로 해제된 청크를 관리한다
fastbin
- singly-linked list - 0x80 이하 size의 chunk를 관리 - mfastptr fastbinsY[10]; 이라는 배열을 통해 0x10, 0x20, 0x30, 0x40, 0x50, 0x60, 0x70, 0x80 사 이즈의 청크를 관리하며 0x90, 0xa0, 0xb0은 사용하지 않는다.
unsorted bin
(분류되지 않은 bin) - circular doubly-linked list small bin 이상의 사이즈가 해제되면 일단 unsorted bin에 등록이 된다. 추후, 새 메모리를 할당 할 때, 할당받길 원하는 크기 이상의 청크가 unsorted bin에 등록이 되어있다면, 바로 반환을 해주고 unsorted bin을 모두 돌아봤지만, 반환해 줄 청크가 없다면, 그때, unsorted bin에 등록되어있던 청크들을 사이즈에 맞게 small bin과 large bin으로 보낸다.
이런 구조로 이루어져 있으며, 기본적으로 주소는 arena의 base주소에 +88을 한 것이기 때문에, 처음 해제한 청크의 fd와 가장 나중에 해제한 청크의 bk에 arena+88의 주소가 들어간다.
small bin & large bin
unsorted bin과 동일한 구조를 가지고 있다. (circular doubly-linked list) unsorted bin에 있던 청크들이 small bin 이나 large bin으로 사이즈에 맞게 옮겨진다.
