What is heap part 2!
오늘도 koreangang의 영상을 보고 정리한 글을 공유하려 합니다.
영상이 매우 짜임새있고, 이해하기 쉬워서 heap을 공부하시는 분들이라면 꼭 봤으면 좋겠네요..ㅎㅎ
지난번에는 heap의 구조에 대해 알아봤다면 오늘은 dlmalloc이 메모리를 어떻게 관리하는지에 대해 알아보겠습니다.
dlmalloc의 알고리즘
dlmalloc의 할당하고, 해제하는 메커니즘은 크게 두가지로 나눌 수 있는데
boundary tag와 binning이 이에 해당합니다.
- chunk의 크기 정보가 chunk의 앞뒤에 저장(boundary tag)
- 재사용 가능한 chunk를 크기 단위로 관리(binning)
boundary tag
-> chunk가 할당될 때 크기 정보가 해당 chunk의 size에 저장됩니다.
이와 같이 할당 받은 chunk는 size가 초기화 되고, prev_size는 초기화 되지 않은 상태입니다.
chunk가 할당될 때 크기 정보가 해당 chunk의 size에 저장된다는 것을 그림을 통해 알 수 있습니다.
그 다음으로
B라는 chunk가 해제가 되면 chunk B의 크기 정보가 바로 뒤 chunk C의 prev_size에 저장됩니다.
이 점을 이용해서 allocated chunk 와 freed chunk가 있을 때
인접한 앞/뒤 chunk의 주소 계산이 가능합니다.
이렇게 B chunk가 해제되어있고, 바로 뒤에 있는 C chunk가 할당되어있을 때
B chunk의 주소는 C chunk의 주소에서 prev_size를 빼면 구할 수 있게 되고, 마찬가지고 C chunk의 주소는 B chunk의 주소에서 prev_size를 더한 주소가 나오게됩니다.
정리를 해보자면 할당된 chunk의 인접한 앞 chunk의 주소는 할당된 chunk - prev_size입니다.
따라서 어떠한 chunk가 있더라도 앞쪽의 chunk가 해제되어있으면 prev_size가 초기화되어있을 것이고, 현재 chunk를 기준으로 prev_size크기를 빼면 이전 chunk의 주소를 계산 할 수가 있습니다.
그 다음으로 임의의 chunk B를 기준으로 인접한 뒤쪽의 chunk의 주소를 계산 할 수도 있습니다.
그림에서 볼 수 있듯이 임의의 chunk B의 size는 allocated, freed 상관없이 항상 초기화가 되어있는 상태이고, 이를 chunk B의 주소에 더하면 뒤쪽으로 할당된 chunk의 주소를 구할 수 있습니다.
따라서 이러한 점을 이용하여 chain형태로 각각의 chunk의 주소를 구할 수도 있게됩니다.
이제 Hacker의 관점에서 바라보면
각각의 정보를 조작하면 다음과 같은 일이 발생합니다.
- prev_size를 조작하면, 이전 chunk의 위치를 조작할 수 있다.
- size를 조작하면 다음 chunk의 위치를 조작할 수 있다.
- prev_inuse bit를 조작하면 이전 chunk의 할당/해제 여부를 조작할 수 있다.
이렇게 조작이 되어서는 안되는 중요한 것들이지만 overflow같은 취약점 혹은 버그로 인해서 조작이 가능하다면 위와 같은 행위가 가능하다는 것을 알 수 있습니다.
자. 이제 dlmalloc의 알고리즘 중 재사용 가능한 chunk를 크기 단위로 관리하는 binning에 대해 알아보겠습니다.
binning
-> dlmalloc이 메모리를 효율적으로 관리하기 위해서 free된 chunk를 크기 단위로 관리하는 방식입니다.
이렇게 free된 chunk를 크기 단위로 관리하여 재사용하여 효율적으로 메모리를 관리합니다.
bin의 종류
binning을 통해 관리되는 chunk를 통상적으로 bin이라고 하고, 이 bin은 크기에 따라 구분될 수 있습니다.
- Fast bin : 작은 크기의 chunk들을 조금 더 빠르게 관리하기 위해서 사용.
- Small bin : 중간 크기(일반적인 크기)chunk를 관리하기 위해 사용.
- Large bin : 큰 크기의 chunk를 관리하기 위해 사용.
- Unsorted bin // 다양한 크기의 chunk들이 사용되기 전에 잠깐 들렸다 가는 곳 / 다양한 용도로 사용됨.
특성\종류 |
Unsorted bin |
Fast bin |
Small bin |
Large bin |
chunk 크기 |
정해지지 않음 |
< 64 (32bit)
< 128 (64bit)
|
< 512 |
>= 512 |
linked list 종류 |
double |
single |
double |
double |
fit 알고리즘 |
exact fit |
exact fit |
exact/best fit |
best fit |
개수 |
10,000 |
10 |
62 |
63 |
입출력 방식 |
FIFO |
LIFO |
FIFO |
FIFO |
Fast bin
정해진 최소 크기에서 8byte 또는 16byte 만큼 커집니다.
- size가 다른 10개의 chunk를 각각 single linked list로 관리(LIFO)
- chunk의 size가 64byte 이하 (32bit 기준), 128byte 이하(64bit 기준)
- 해제가 되어도 다음 chunk의 prev_inuse bit가 변경되지 않는다.
-> 인접한 chunk와 병합되지 않음
이 fast bin의 크기는 32bit, 64bit에 따라 다릅니다.
그리고 fast bin은 최대 10개의 chunk를 single linked list로 관리합니다.
일반적으로 small bin, large bin과는 다르게 LIFO(Last In First Out)구조를 갖고있습니다.
특이한점은 해제가 되어도 다음 chunk의 prev_inuse bit가 변경되지 않는다는 점입니다.
이 의미는 인접한 chunk와 병합이 되지 않는다는 것인데, 자세한 내용은 밑에 정리하겠습니다.
그리고 이러한 bin들은 크기 단위로 구분짓는 것이 좋고, 그 크기가 32bit에서는 64byte이하, 64bit에서는 128byte이하입니다.
이렇게 중요한데 과연 그럴지 궁금하지 않나요..?ㅎ
직접 확인해 봐야겠죠?
#include <stdio.h>
#include <stdlib.h>
int main(void)
{
char *p1 = malloc(32);
char *p2 = malloc(32);
char *p3 = malloc(32);
free(p2);
return 0;
}
해당 코드를 다음과 같이 gcc 컴파일 해줍니다.
이후 gdb를 이용하여 확인을 해보면 알 수 있는데,
free() 이후 bp를 걸고 heap을 살펴보면 알 수 있습니다.
0x804b15c에 위치한 size를 보시면 malloc()을 통해 할당 받은 size가 32(0x30 = header size + mem size)임에 반해 31로 초기화 되어있는 것을 확인 할 수 있습니다. 따라서 해제를 했지만 prev_inuse bit가 1로 설정이 된 것을 확인 할 수 있는 것입니다.
Small bin
다음으로 small bin에 대해 살펴보겠습니다.
- size가 다른 63개의 chunk를 double linked list로 관리(FIFO)
- chunk의 size가 512byte 이하
- 해제가 되면 뒤 chunk의 prev_inuse bit clear
-> free할 때 인접한 freed chunk와 병합
small bin은 서로다른 크기의 63개의 chunk가 double linked list로 관리됩니다.
fast bin과 달리 FIFO(First In First Out)구조로 chunk를 관리합니다.
chunk의 size는 총 512byte 이하입니다.
또 fast bin은 해제가 되어도 prev_inuse bit가 변하지 않았지만 small bin의 경우 변경이 됩니다.
그러므로 일반적으로 관리되는 chunk인 small bin은 인접한 chunk가 해제되어있으면 병합이 됩니다.
Large bin
다음으로 large bin입니다.
- 특정 범위의 size가 다른 63개의 chunk를 double linked list로 관리(FIFO)
- 크기가 512byte 이상 되는 chunk이고, 범위 내에서 size가 큰 chunk가 제일 앞
- 해제가 되면 뒤 chunk의 prev_inuse bit clear
-> free할 때 인접한 freed chunk와 통합
large bin은 small bin과 fast bin처럼 정확한 크기 단위로 관리되는 것이 아니라 chunk의 크기를 범위 단위로 관리합니다.
원래 하나의 linked list내에서는 동일한 크기를 관리하는데, large bin은 다른 size도 포함하여 관리합니다.
small bin과 같이 free할 때 인접한 freed chunk와 통합됩니다.
그리고 해당 size 범위 내에서 가장 큰 chunk가 가장 앞에 있다는 것을 알고 있어야 합니다.
가장 큰 chunk가 앞에 있도록 정렬하고, 다른 크기의 chunk를 가리키는 포인터는 따로 관리되는데요.
fd_next_size와 bk_next_size에 이 포인터가 존재하여 다른 크기를 가리키도록 되어있는 형태입니다.
다음과 같이 하나의 linked list내에 다른 크기를 가리키는 포인터 fd_next_size, bk_next_size라는 포인터가 존재하여 다른 크기를 가리키도록 되어있습니다.
large bin의 경우 다른 bin과 달리 서로 다른 크기의 chunk를 범위 단위로 관리하기 때문에 별도의 포인터가 존재한다는 것을 알고가시면 됩니다.
Unsorted bin
unsorted bin은 여러가지 경우에 unsorted bin에 들어가게 되는데 다음과 같습니다.
# unsorted bin에 들어가는 경우
- free 했을 때 각 bin(small bin, large bin)으로 들어가기 전 / fast bin은 제외
- fast bin들이 병합(malloc_consolidate)되어 합쳐지면
- bestfit으로 할당 된 chunk의 남은 부분이 remainder
- 인접한 chunk도 이미 free되어 있어, 병합(consolidate)된 free chunk
#unsorted bin에서 나오는 경우
- 사용자가 malloc을 호출하여 요청한 size와 동일한 chunk가 있으면
풀어서 설명을 하면
처음 free를 했을 때 fast bin을 제외한 chunk는 해당 bin에 바로 들어가는 것이 아니고, unsorted bin에 먼저 들어가게 됩니다.
그 다음으로 fast bin은 인접한 chunk가 해제 되었을 때 prev_inuse bit가 변경되지 않아서 병합이 되지 않는데
fast bin들은 특정 상황(ex. 크기가 큰 size의 chunk를 요청받았을 때)에 붙어있는 fast bin에 포함되어 있는 chunk들을 한번에 합쳐버립니다.
small bin, large bin은 인접한 두개의 chunk를 합치는데 fast bin은 여러개의 chunk를 합치게 됩니다.
이 부분을 malloc_consolidate라고 표현하고 이 함수가 malloc.c 내에 구현되어있습니다.
그리고 fast bin이 병합되어야할 때 이 함수가 호출됩니다.
다음으로 bestfit으로 할당 된 chunk의 남은 부분 remainder가 unsorted bin에 들어가게 되는데요.
예를 들어 140byte의 크기를 가진 chunk가 free가 되어있고, 사용자가 100byte를 요청하면 해당 chunk(140byte)를 잘라서 남은 부분인 40byte는 unsorted bin으로 들어가고, 100byte를 반환하게 됩니다.
따라서 이러한 remainder를 관리하기 위해 unsorted bin을 이용합니다.
마지막으로 인접한 chunk가 이미 free되어있고, 해당 chunk가 free될 때 연속된 두 chunk가 free되는 것이므로 그 두개의 chunk를 합치게 됩니다.
이를 병합이라 하고 이렇게 병합된 chunk도 unsorted bin에 들어가서 관리됩니다.
unsorted bin에서 나오는 경우는 여러가지가 있지만 가장 대표적으로는 사용자가 malloc을 호출하여 요청한 size와 동일한 chunk가 unsorted bin내에 존재할 경우 나오게됩니다.
지금까지 boundary tag와 binning에 대해 배워봤습니다.
이제 병합과정에 대해 배워봅시다.
병합(consolidate)
-> 해제(free)하려는 chunk의 앞, 뒤 chunk가 이미 해제 되어있을 때 병합이 발생한다.
다음 그림은 chunk B를 해제하려고 했을 때의 병합 과정을 설명해주는 그림이다.
chunk B를 기준으로 앞에 위치한 chunk A가 이미 해제되어있을 때
chunk B를 해제하면 이전 chunk A의 prev_inuse bit를 확인하고 할당/해제 여부를 판단합니다.
그리고 이전 chunk가 해제 되었다면 현재 chunk의 prev_size가 초기화 되어있을 것이므로 해당 chunk의 주소에서 prev_size를 빼면 앞의 chunk 즉 chunk A의 주소를 구할 수 있게 됩니다.
따라서 chunk A와 chunk B의 주소를 모두 알고, 현재 상태를 모두 알기 때문에 이 두개를 합치게 됩니다.
그 다음으로 chunk A의 뒤 chunk B가 이미 해제되어있고, A를 해제 하려고 했을 때 어떻게 병합이 되는지 과정을 보겠습니다.
A의 주소에서 chunk A의 size를 더해서 chunk B의 주소로 가고, 한번 더 같은 과정을 거쳐 C의 주소로 이동합니다.
그 이유는 특정 chunk의 할당/해제 여부는 그 다음 chunk에 있기 때문입니다.
그러므로 B의 할당/해제 여부는 chunk C에 있습니다.
# chunk B가 할당 되어있다면?
C의 prev_size는 초기화 되지 않고, size의 prev_inuse bit 또한 변하지 않고 1을 유지한다.
# chunk B가 해제 되어있다면?
C의 prev_size는 초기화 되고, size의 prev_inuse bit 또한 0으로 초기화 된다.
위의 정보를 이용해서 B가 할당되었는지 해제되어있는지를 판단하게 됩니다.
따라서 chunk A를 해제 하려고 할 때 해당 chunk의 size를 더하고, 다음 chunk의 size를 또 더해서 C의 주소를 계산한 뒤에 C에서 C의 prev_inuse bit를 확인하여 0이라면 C앞에 있는 chunk B가 해제되었다는 것을 판단하게 되는 것입니다.
이러한 과정으로 병합이 되고, 이렇게 병합을 하기 전 freed chunk에는 linked list로 관리하기 위해 fd, bk가 존재합니다.
이 fd와 bk 포인터를 정리를 해줘야합니다.
이를 unlink 라고 표현합니다.
-> bin list에 등록된 chunk를 제거하기 위해 포인트 fd, bk를 정리하는 작업
위 그림과 같이 병합에 의해 가운데 있는 chunk가 bin list에서 제거 되어야하는 상황입니다.
이 때 제거되는 해당 chunk의 fd와 bk를 이용해서 계산하고, 채워주는 과정을 unlink라고 합니다.
chunk B의 fd는 chunk A를 가리키고 있고, bk는 chunk C를 가리키고 있는 상황에서
B가 제거되는 unlink가 진행되면
A의 bk는 더이상 B가 아니기 때문에 B의 bk값을 가져와 A의 bk에 세팅합니다.
그리고 C의 fd는 더이상 B가 아니기 때문에 B의 fd를 가져와 C의 fd에 세팅합니다.
#define unlink( P, BK, FD ) {
BK = P->bk;
FD = P->fd;
FD->bk = BK;
BK->fd = FD;
}
이는 위 매크로에 의해 진행되고, 다음에 배울 double free bug 취약점을 다룰때 더 알아보도록 하고 넘어갑시다 :)
지금까지
boundary tag에서 prev_size, size, prev_inuse 에 대해 살펴보았고, 이 세개의 값을 조작하면 주소를 계산할 때 조작을 가능하게 하거나 이전 chunk의 할당/해제 여부를 조작할 수 있게 됩니다.
다음으로 binning에서는 unsorted bin, fast bin, small bin, large bin, consolidate(unlink)에 대해 알아봤고,
이제 how2heap을 이해하며 heap공부를 계속하시면 될 것 같습니다.
이상 포스팅을 마칩니다.
-즐헼!-
