728x90

Heap 기초2

이번에는 청크가 어떠한 구조로 되어있는지 자세하게 알아볼 것이다

1. Chunk

malloc() 함수가 호출됨으로서 할당받는 영역을 청크라고 부른다. 32bit에서는 해당 청크가 8byte 단위로 할당이 되고, 64bit에서는 16byte 단위로 할당된다. 일반적으로 malloc()을 호출하고 반환되는 주소를 이용하여 데이터를 입력하게 되는데, 사실 반환되는 주소는 청크의 시작부분이 아닌 페이로드의 주소이다.

페이로드바로 위에 meta-data를 포함하는 청크 헤더가 존재한다. 이 헤더에서 현재 청크의 사이즈가 몇인지, 인접한 청크의 사이즈는 얼마인지가 들어있다.

청크는 크게 3가지 타입을 가진다. 기본 구조는 동일하며 약간의 내용물의 차이가 있다.

1.1 Allocated Chunk(할당되어 있는 청크)

하나 알아둬야할 점은, malloc을 통해 할당된 청크는 prev_size, size, payload 이렇게 구성되어 있는데, 다음 다음 청크의 prev_size 필드도 현재 청크의 페이로드 필드로 사용된다. 따라서 실질적인 청크는 다음 청크의 prev_size까지 포함되며, free시에는 해당 영역은 현재 청크의 크기를 중복하여 저장하는 용도로 사용한다.

Prev_size
만일 해당 청크 바로 이전 청크가 해제된 경우, 이 필드는 이전 청크의 크기를 저장한다. 만약 아무런 해제된 청크가 없고 죄다 할당된 청크이면 해당 필드는 기본값인 0으로 세팅된다.

Size
이 필드에는 현재 할당된 청크의 크기를 저장한다. 64bit에서는 malloc 사이즈를 16byte 단위로 저장한다고 했기때문에 하위 3bit는 항상 0으로 고정된다.
```
예를 들어 16-byte alignment에서 가능한 사이즈를 살펴보면:

00000000 00010000 = 16바이트
00000000 00100000 = 32바이트
00000000 00110000 = 48바이트
```
따라서 하위 3bit를 이용하여 부가적인 정보의 표현이 가능하다.
1. NON_MAIN_ARENA(A) - 현재 청크가 thread_arena에 위치하는 경우 1로 세팅됨
1. IS_MMAPPED(M) - 현재 청크가 mmap을 통해 할당된 경우 1로 세팅됨. 큰 메모리를 요청하는 경우에는 heap을 이용하지 않고, mmap() 시스템 콜을 통해 별도의 메모리 영역을 할당함. 이러한 청크들은 bin 내에 속하지 않음. free시 그냥 munmap() 호출로 해지함
1. PREV_INUSE(P) - 현재 청크 바로 이전의 청크가 할당되어 있는 경우 1로 세팅됨

1.2 Free Chunk(해제된 청크)

우선 free된 청크들은 단일 free 청크로 결합된다는 특징이 있다. 이를 염두해두고 free 청크 구조를 알아보자

Prev_size
아까 위에서 해당 필드에 대해 설명을 했었다. 사실 free 청크에서 해당 필드가 사용된다. 위 그림을 보면 노란색 부분이 free 청크 영역이다. 맨 아래에 Prev_size가 포함된 것을 확인할 수 있는데, 이는 Next Chunk의 일부임으로 현재 Chunk의 사이즈와 동일한 값이 들어간다. 이를
boundary tags
기법이라고 한다. 왜 필요한지 다음 그림을 한번 보자

현재 청크 A가 free된 상태이고 청크 B는 할당되어 있는 상태이다. 이 상태에서 청크 B가 free 되려고 한다. 이전 A 청크가 free된 상태이기 때문에 B를 free한 뒤 A와 결합하여 하나의 free 청크로 만들것이다.

그렇다면, 청크 B 기준으로 어디까지 A청크인지, A청크가 진짜 free된 청크인지 flag 비트를 확인해야한다. 따라서, free된 청크는 맨 아래에 현재 청크의 동일 크기인, 사이즈를 복사해야한다.

결국, A가 free되었을때 현재 청크의 사이즈가 맨 아래에 복사가 될 것이고, 이는 다음 청크의 prev_size 필드에 저장된다. 따라서 B 청크가 free될시 A 청크의 크기를 확인하여 결합을 진행할 수 있게 된다. 또한 prev_size에 들어가는 값은 P(PREV_INUSE) 플래그가 제거되어 들어간다.
```
<예외사항>

참고로 fastbins의 경우에는 free 청크들끼리 결합하지 않으므로 해당 free 되어도 boundary tags를 
세팅하지 않는다. (틀리면 말해주세요..) bin과 관련된 설명은 추가적으로 자세히 할 예정이다. 지금은 
그냥 그렇구나 하고 넘어가시길..
```

Fd(forward pointer), Bk(backward pointer)
fd와 bk는 각각 해제된 다음 청크, 해제된 이전 청크를 가리키는 포인터이다. 이러한 포인터들은 단일 연결 리스트, 혹은 이중 연결 리스트 형태로 구현되어있다. bins들에서 free 청크가 관리되는데 지금은 그냥 그렇다고 알고만 있고, 아래 그림을 봐보자

빈에 free된 청크들이 이중 연결 리스트로 연결되어 있다. fd, bk가 각각 이전 청크를 가리키기때문에 전체 free청크들을 순회하여 확인 가능하다. 여기서 헷갈리면 안되는 것이 있다. 빈에 등록된 free 청크들은 물리적으로 붙어있는 것이 아닌,

위 그림처럼 논리적으로 리스트를 이용하여 연결을 시켜놓은 것이다. 빈이 free 청크들을 관리하기 위한 방법으로 이렇게 실제 힙에서 free된 청크에 대한 정보를 이중 연결 리스트로 연결시킨다. (fastbins은 단일 연결 리스트로 관리함)

fd_nextsize, bk_nextsize
bin은 free된 청크들을 관리하는 곳이라고 했다. 이 빈들도 free 청크들의 사이즈에 따라 크게 fastbins, unsorted bin, small bin, large bin 이렇게 총 4개로 나뉜다. 각 빈들에 대해서는 추후 자세히 설명할 것이다. 이중 fd_nextsize, bk_nextsize 포인터는 가장 큰 free 청크를 관리하는 largebin을 위해서만 사용된다.

large bin에서만 해당 포인터들이 필요한 이유는, large bin을 제외한 다른 빈들의 각 인덱스에는 동일 사이즈의 청크들로 리스트가 형성된다. 하지만 large bin은 연결리스트에 크기를 대략적으로 관리하기 때문에 청크들의 사이즈를 알아야 관리가 가능하기 때문이다.

1.3 Top chunk

Top Chunk는 Arena의 가장 상위 영역에 있는 청크이다. 맨 처음 malloc 호출시 사용자가 요청한 사이즈 만큼만이 아닌, 충분한 크기의 메모리를 받아온다. 그리고 이 사이즈를 Top chunk에 넣는다.

free chunk들이 메모리 할당 요청을 만족하지 못하는 경우, Top 청크를 분할하여 요청을 처리하는데 2개로 분할된다.
1. User chunk(사용자가 요청한 크기)
1. Remainder chunk(나머지 크기) - 이게 새로운 Top 청크가 됨

만약 현재 top 청크 크기보다 더 큰 사이즈를 요청하는 경우, main_arena의 경우 sbrk로 top 청크의 크기를 확장시키고, thread_arena의 경우는 mmap으로 새롭게 메모리를 받아온다.

2. 실제로 Chunk 구조 확인하기

이번에는 실제로 위에서 설명한 내용들을 디버깅하여 눈으로 직접 확인해보자. 테스트 환경은 우분투 16.04 LTS 버전이고 테스트 코드는 다음과 같다.

  1 #include <stdio.h>
  2 #include <stdlib.h>
  3 #include <string.h>
  4 int main()
  5 {
  6         char* a=(char*)malloc(0x20); //0x602010
  7 
  8         char* b=(char*)malloc(0x14); //0x602040
  9 
 10         char* c=(char*)malloc(0x30); //0x602060
 11 
 12         char* d=(char*)malloc(0x14); //0x6020a0
 13 
 14         char* e=(char*)malloc(0x22); //0x6020c0
 15 
 16         strcpy(a,"AAAAAAAA");
 17         strcpy(b,"BBBBBBBBBBBBBBBBBBBB");
 18         strcpy(c,"CCCCCCCC");
 19         strcpy(d,"CCCCCCCC");
 20         strcpy(e,"BBBBBBBB");
 21 
 22         free(b);        // fastbin fd, bk checking
 23         free(d);        // fastbin fd, bk checking
 24 
 25         char* sg=(char*)malloc(0x100);
 26         strcpy(sg,"SSSSSSSS");
 27         free(sg);       // prev_size checking
 28 
 29         char* z=(char*)malloc(0x100);
 30         char* test=(char*)malloc(140000);       // mmap'd flag checking
 31         free(test);
 32         return 0;
 33 }

사실 bin에 대한 개념을 제외하고 해당 코드를 설명하기는 힘들지만, 최대한 제외하고, 여태 설명한 것을 눈으로 직접 확인해보겠다. 그래야 더 이해가 잘된다.ㅇㅇ

bp 설정 라인

6. char* a=(char*)malloc(0x20);

20 strcpy(e,"BBBBBBBB");

22 free(b); // fastbin fd, bk checking

23 free(d); // fastbin fd, bk checking

30 char* test=(char*)malloc(140000);

31 free(test);

2.1 malloc 호출시 기본 청크 구조

1) 6. char* a=(char*)malloc(0x20); 호출 직후

맨 처음 malloc이 이뤄질시, 현재 free 청크들도 없고, 힙영역이 할당되어 있지 않기 때문에 brk를 이용하여 메모리를 할당받을 것이다.

위 알고리즘은 malloc 호출시에 실행되는 구조이다. 구조적으로 봤을때 맨 처음 malloc을 호출하였기 때문에 아래의 어떠한 조건도 해당되지 않을 것이며, Top 청크 또한 0일 것이다. 따라서 sysmalloc이 호출될 것이다. 6라인에 bp를 걸고 b* brk를 입력한뒤 실행시켜보자

brk에 bp가 정상적으로 걸린것을 확인 할 수 있다. 또한 backtrace로 호출 과정을 살펴보면, 위 알고리즘의 sysmalloc을 호출하고 sbrk→brk를 호출하는 것을 확인 가능하다. malloc 호출이 종료되면 다음과 같다.

top chunk의 사이즈가 0x20fd1로 세팅되어 있다. 또한 이전 free된 청크가 없기 때문에

prev_size 가 0으로 세팅되어 있다. 사용자에게 반환되는 주소는mem위치로 현재 0x602010 주소가 될 것이고, 여기에 실제 입력하는 데이터가 들어간다.

현재 청크 사이즈는 요청 사이즈(0x20) + chunk의 header 0x10 = 0x30 이다. 근데 prev_in use 비트가 1로 세팅되어 있는 걸 확인할 수 있다. 이전 할당된 청크가 없지만, 이건 그냥 glibc 2.23 malloc.c 소스코드를 보면, sysmalloc 부분에서 1로 세팅하는 걸 확인 가능하다.(자세하게는 모르겠다..)

2) 20. strcpy(e,"BBBBBBBB"); 호출 직후

5개의 할당된 청크에 모두 데이터가 들어가 있는 것을 확인해보자.

처음 탑 청크의 사이즈가 0x20f21에서 0x20f21로 변한것을 확인할 수 있다. 5개의 할당된 청크사이즈를 다 더해서 0x20f21에서 뺴면 0x20f21이 나온다.

위 그림을 보면, 각 청크별로 초록색으로 구분을 지어놨다. 하지만 아까 청크설명부분에서 다음 청크의 prev_size도 현 청크의 페이로드부분으로 들어간다고 했으므로, 청크 b의 데이터영역이 청크 c의 prev_size 필드까지 들어간다는것(0x602050)을 확인 가능하다.

3) 22 free(b); 호출 직후 // fastbin fd, bk checking

처음으로 free가 호출된 직후 메모리 상황이다. 달라진점은 청크 b의 fd 필드가 0으로 초기화 된것 말고는 없다. 그 이유는 fastbin 설명때 자세히 하겠다. 또한 현재 fastbin에 free한 청크의 주소가 들어가 있다.

4) 23. free(d); 호출 직후 // fastbin fd, bk checking

두번째 free가 호출된 직후 메모리 상황이다. 현재 청크 b와 d가 free된 상태인데 d의 fd포인터에 b의 주소가 들어가 있는 것을 확인 가능하다. fastbin 리스트를 한번 확인하자

fastbin[0] → 청크 d → 청크 b 로 연결되어 있는 것을 확인 가능하다. 이부분 역시 지금은 그냥 넘어가자.

5) 30. char* test=(char*)malloc(140000); 호출 직후

위 사진의 주소를 보면 기존에 할당받아왔던 0x6020.. 위치의 주소가 아니다. 또한 하위 2번째 bit가 1로 세팅되어 있기 때문에 mmap으로 할당받은 영역인것을 확인할 수 있다. 그럼 이 영역이 어느영역에 위치하는지 vmmap으로 확인해보자.

mapped 되어있는 영역에 할당받은것을 확인 할 수 있다. 이 이유는 위에서 설명한대로, top chunk보다 큰 사이즈를 요청할 경우 mmap syscall로 메모리를 할당받기 때문이다. 해당 영역은 단일 청크로 사용이 되며, free시 munmap으로 해제하기 때문에 free이후에는 디버깅이 불가하다. 이는 backtrace로 확인이 가능하다.

6) 31. free(test); 호출 직후

위 사진 처럼 free 이후에는 디버깅이 불가능하다.

vmmap으로 확인해보면 해당 메모리 영역이 반환되어 없어진 것을 볼 수 있다.

3. 결론

저번 포스팅에는 힙에 대한 전체적인 개념에 대해서 공부했다면, 이번 포스팅은 청크의 구조부터 실질 데이터의 삽입 과정을 눈으로 확인해보았다. 이제 마지막으로 free list들을 관리하는 빈에 대해서 공부한 내용을 정리하고, 힙 문제를 풀어볼 예정이다.