우선 chunk는 malloc() 함수가 호출됨으로서 할당받는 영역을 chunk라고 부른다.
32bit에선 chunk가 8byte 단위로 할당이 되고
64bit에서는 16byte 단위로 할당이 된다.
chunk는 크게 3가지 타입을 가진다.
기본 구조는 동일하며 약간의 내용물의 차이가 있다.
1. Allocated Chunk (할당되어 있는 청크)
우선 Allocated Chunk의 Structure부터 살펴보자
- 1. Prev_size -
만일 해당 chunk 바로 이전 chunk가 해제된 경우, Prev_size에는 이전 chunk의 크기를 저장한다.
만약 아무런 해제된 chunk가 없고 죄다 할당된 chunk라면 Prev_size는 기본값인 0으로 바뀐다.
- 2. size -
size field에서는 현재 할당되어 있는 chunk의 size를 저장한다.
64bit에서는 malloc size를 16byte 단위로 저장한다고 했기 때문에
하위 3byte는 항상 0으로 고정되기 때문에 이를 이용해서
부가적인 정보(A, M, P)를 표현할 수 있다.
⦁ NON_MAIN_ARENA (A)
현재 chunk가 thread_arena에 위치하는 경우 1로 셋팅
⦁ IS_MMAPPED(M)
현재 chunk가 mmap을 통해 할당된 경우 1로 셋팅.
⦁ PREV_INUSE(P)
현재 chunk 바로 이전의 chunk가 할당되어 있는 경우 1로 셋팅
allocated chunk는 대략 이렇게 이루어져있다.
이제 free chunk에 대해서 알아보자.
2. Free Chunk (해제된 청크)
free된 chunk들은 단일 free chunk로 결합된다는 특징이 있다.
- 1. Prev_size -
Prev_size는 allocated chunk 부분에서도 설명을 했었다.
이 필드가 실제로 사용되는 곳은 free chunk이다.
위 사진을 보면 맨 아래에 Prev_size가 포함된 것을 확인 할 수 있는데,
이는 Next Chunk의 일부임으로 현재 Chunk의 사이즈와 동일한 값이 들어간다.
우리는 이를
boundary tags 기법이라고 부른다.
chunk A는 free된 상태이고, chunk B는 malloc 되어있는 상태이다. 이 상황에서 chunk B를 free 시키려고 한다.
이전 A chunk가 free된 상태이기 때문에 Chunk B를 free한 뒤 A와 결합하여 하나의 free chunk를 만들려고한다.
※ free된 chunk들은 단일 free chunk로 결합된다는 특징이 있다.
그렇다면, chunk B 기준으로 어디까지 Chunk A인지, Chunk A가 진짜 free된 chunk인지 flag bit를 확인해야한다.
따라서 free된 chunk는 맨 아래에 현재 chunk의 동일 크기인, size를 복사해야한다. (boundary_tags)
최종적으로, A가 free되었을 때 현재 chunk의 size가 맨 아래에 복사가 되고, 이는 다음 chunk의
prev_size에 저장이 된다.
그럼 Chunk B가 free 될때에는 Chunk A의 size를 확인하여 결합이 될 수 있다.
+ prev_size에 들어가는 값은 P(PREV_INUSE) FLAG가 제거되어 들어간다.
- 2. FD, BK -
fd와 bk는 각각 해제된 다음 chunk, 이전 chunk를 가리키는 포인터이다.
이러한 포인터들은 단일 연결 리스트, 이중 연결 리스트 형태로 구현되어 있다.
chunk가 free되면 bin이라는 구조에 들어가서 연결리스트로 이어진다.
위와 같이 chunk가 free 되어서 fd와 bk라는 것으로 free chunk를 이어주게 된다.
그래서 재할당을 할 때에 bin에서 free chunk를 순회하며 확인 가능하다.
- 3. fd_nextsize, bk_nextsize -
bin도 free된 chunk의 크기에 따라서 여러가지 종류로 나뉘는데,
fd_nextsize, bk_nextsize는 free_chunk중 가장 크기가 큰 chunk들을 관리하는 large bin에서만 사용한다.
free chunk에 대한 설명은 여기까지다. Top chunk로 넘어가자
3. Top Chunk
Top chunk는 단어 그대로 arena의 가장 상위 영역에 있는 chunk를 말한다.
맨 처음 malloc 호출 시 사용자가 요청한 사이즈 만큼만 할당해주는 것이 아니라
(사용자가 요청한 메모리 + α)로 할당해준다. 그리고 이 사이즈를 Top Chunk에 넣는다.
그리고 malloc을 다시 사용할 때에는 free chunk들이 모인 bin에서 메모리 할당 요청을 하는데
만족하는 크기가 없다면 Top chunk를 분할하여 요청을 처리한다.
그래서 Top chunk를 2개로 분리한다.
1. User chunk (사용자가 요청한 크기)
2. Remaider chunk (나머지 크기) -> 새로운 Top chunk
하지만 만약 bin에서도 원하는 크기를 찾을 수 없고 Top Chunk보다 큰 크기를 할당하여서
분할 할 수도 없는 상황에 놓인다면 main_arena는 sbrk로 Top chunk의 크기를 확장시키고
thread_arena는 mmap으로 새로운 메모리 구역을 할당받는다.
4. Code로 chunk 구조 확인하기
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int main()
{
char* a=(char*)malloc(0x20); //0x602010
char* b=(char*)malloc(0x14); //0x602040
char* c=(char*)malloc(0x30); //0x602060
char* d=(char*)malloc(0x14); //0x6020a0
char* e=(char*)malloc(0x22); //0x6020c0
strcpy(a,"AAAAAAAA");
strcpy(b,"BBBBBBBBBBBBBBBBBBBB");
strcpy(c,"CCCCCCCC");
strcpy(d,"CCCCCCCC");
strcpy(e,"BBBBBBBB");
free(b); // fastbin fd, bk checking
free(d); // fastbin fd, bk checking
char* sg=(char*)malloc(0x100);
strcpy(sg,"SSSSSSSS");
free(sg); // prev_size checking
char* z=(char*)malloc(0x100);
char* test=(char*)malloc(140000); // mmap'd flag checking
strcpy(test, "AAAAAAAA");
free(test);
return 0;
}하나하나 살펴보자
1. 첫번째 break point -> main + 18
첫번째 break point는 main + 18로 잡았다.
main + 18은 a에 malloc(0x20) 직후이다.
0x20을 요청했지만 그것보다 더 큰 크기인 0x30이 할당되었고
이전에 free된 chunk가 없어서 prev_size, fd, bk가 0으로 셋팅되어 있다.
그리고 top chunk의 size가 0x20fd0으로 할당이 되어있는데,
이는 위에서 말했던것처럼 malloc시 top chunk에서 분할하여 할당하기 때문에
top chunk의 원래 사이즈 (0x21000) - 할당된 메모리 사이즈(0x30) = 현재 top chunk 사이즈 (0x20fd0)
이런 식으로 된다.
2. 두번째 break point -> main + 197
두번째는 e에 "BBBBBBBB"라는 문자열을 넣은 직후이다.
이는 모든 chunk에 데이터가 들어갔을것이고 top chunk의 사이즈도 변했을것이다.
top chunk의 사이즈가 변했는데 잘 보면 chunk c에 chunk b의 데이터 영역이 prev_size에 들어갔다는거다.
이 부분이 이해가 잘 안가서 찾아봤는데, 다음 chunk의 prev_size 필드도
현재 chunk의 데이터 영역으로 사용된다고 한다.
사알짝 이해가 안가서 계속해서 찾아봐야될거 같다
3. 세번째 break point -> main + 228
main + 228은 b, d가 free되고 직후이다. fastbin과 fd, bk를 주의깊게 보자
b, d가 free 된 것을 볼 수 있다. 그러면 bin 구조는 이렇게 된다.
그러면 b의 fd에는 0x0이 들어가있고,
c의 fd에는 b의 주소가 들어가있다.
fastbin에는 chunk d -> chunk b로 연결되어 있다.
이 부분은 나중에 bin 정리할때 왜 b의 fd가 0x0인지 bin의 구조가 왜 이렇게 되어있는지
다시 한번 정리할 생각이다.
그냥 지금은 free 되면 bin 이라는 곳에 chunk가 들어간다고 생각하면 될거 같다.
4. 네번째 break point -> main + 299
main + 229는 test에 top chunk보다 큰 크기를 malloc한 직후이다.
parseheap에는 안잡혀서 free할때 rdi 인자보고 직접 주소 확인했다.
0x7ffff7fb3000 영역에 할당이 되었고, 0x7ffff7fb3008 부분을 보면 하위 2번째 bit가 1로 셋팅되어 있어서
top chunk보다 큰 크기를 요청하였을때는 mmap으로 메모리를 할당받는것을 알 수 있다.
해당 영역은 단일 chunk로 사용이 된다.
references
https://wogh8732.tistory.com/179?category=699165
http://www.cs.cmu.edu/afs/cs/academic/class/15213-s12/www/lectures/18-allocation-basic-1up.pdf
'Heap' 카테고리의 다른 글
| ptmalloc free & bin (0) | 2021.10.20 |
|---|---|
| Dynamic memory allocator (glibc malloc) (0) | 2021.10.15 |