메모리를 할당할때 어떤 일이 일어나는지 정리했으니까
이번에는 free를 호출할때 어떤 일이 일어나는지 보자
1. What is BIN?
우선 bin이 무엇인지 알아보자
우리는 c언어에서 malloc과 free를 이용하여서 동적으로 메모리를 관리한다.
만약 malloc을 이용하여서 메모리를 할당하고 free를 이용하여 free chunk를 만들어준다면
이 free chunk는 bin이라는 구조에 들어가게 된다.
bin은 크게 4가지 종류로 나뉜다.
1. fast bin
2. unsorted bin
3. small bin
4. large bin
bin들에 대한 정보는 malloc_state 구조체에서 확인 할 수 있다.
struct malloc_state
{
/* Serialize access. */
mutex_t mutex;
/* Flags (formerly in max_fast). */
int flags;
/* Fastbins */
mfastbinptr fastbinsY[NFASTBINS];
/* topchunk의 base address */
mchunkptr top;
/* 가장 최근의 작은 요청으로부터 분리된 나머지 */
mchunkptr last_remainder;
/* 위에서 설명한대로 pack된 일반적인 bins */
mchunkptr bins[NBINS * 2 - 2];
/* Bitmap of bins */
unsigned int binmap[BINMAPSIZE];
/* 연결 리스트 */
struct malloc_state *next;
/* 해제된 아레나를 위한 연결 리스트 */
struct malloc_state *next_free;
/* 현재 Arena의 시스템으로부터 메모리 할당 */
INTERNAL_SIZE_T system_mem;
INTERNAL_SIZE_T max_system_mem;
};
중요한거 몇가지만 보면
fastbinsY : fast bin을 관리함
bins : bin은 127개가 존재하는데 가장 처음 빈은 unsorted bin, 나머지 126개가 unsorted bin, small bin, large bin.
allocated chunk는 chunk size에 따라서 구분된다.
위에서 말하는 chunk size는 chunk 구조체에 있는 size field를 말하는거다.
chunk들의 속성은 이와 같다.
이러한 bin들이 존재하는 이유는 ptmalloc에서 malloc을 요청하면 항상 메모리 할당을 요청하는 것이 아닌
이전에 free chunk가 되어서 bin에 들어간 chunk들을 재활용하기 위해서이다.
만약 사용자가 요청한 특정 사이즈의 chunk가 bin에 존재한다면 재활용한다.
그리고 이전 글에서도 말했었는데 물리적으로 인접해있는 free chunk들은
일반적으로 서로 병합을 하여서 큰 free chunk를 만들려고 한다.
그래서 free chunk가 병합을 할 때는 대표적으로 다음 chunk와 결합하는 경우,
이전 chunk와 결합하는 경우가 있다.
- 다음 chunk와 결합하는 경우 -
이 상황에서 Chunk A를 free 시키면 우리는 B Chunk가 이미 free chunk인것을 알기 때문에
병합이 될 거라는 것을 안다. 하지만 A chunk 입장에서 봤을때 B chunk가 free chunk인지
allocated chunk인지 모르기 때문에 C chunk의 P(prev_inuse) flag를 확인해야 한다.
만약 C chunk의 P flag bit가 0으로 설정이 되어 있다면 이전 chunk인 B가 free chunk임이
틀림없기 때문에 P flag를 확인하고 A chunk가 B chunk와 병합을 진행하게 된다.
요런식으로 병합이 된다.
- 이전 chunk와 병합하는 경우 -
지금은 B chunk가 할당되어 있는 경우이고, free 시킬려고 한다.
그러면 이 경우는 B chunk는 자신의 P flag를 확인하여 0이 셋팅이 되어 있다면
A chunk가 free chunk임이 확실해지니까 A와 병합을 진행하게 된다.
이제 위에서 언급했던 각 bin들에 대해서 정리하자.
2. Fast bin?
같은 크기를 기준으로 단일 연결 리스트로 연결된 일정 크기 이하의 작은 chunk들을 의미한다.
fast bin의 특징은 이와 같다.
※ LIFO 방식 사용 (= Stack)
※ 10개의 bin을 사용한다.
※ 속도 향상을 위해 단일 연결 리스트로 구성됨. 다른 bin들은 다중 연결 리스트로 구성됨
※ fast bin이 처리하는 메모리의 최대 크기는 global_max_fast에 의해서 결정됨 (default = 64byte)
※ 32bit : bin size는 최소 16byte부터 64byte 까지이다.
※ 64bit : bin size는 최소 32byte부터 128byte 까지이다.
※ fast bin의 경우 free chunk가 서로 인접해 있어도 병합이 일어나지 않는다.
코드로 디버깅하면서 살펴보자
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int main()
{
char* a=(char*)malloc(0x10);
char* b=(char*)malloc(0x20);
char* b2=(char*)malloc(0x25);
char* c=(char*)malloc(0x30);
char* d=(char*)malloc(0x40);
char* d2=(char*)malloc(0x45);
char* e=(char*)malloc(0x50);
char* f=(char*)malloc(0x60);
char* g=(char*)malloc(0x70);
free(a);
free(b);
free(b2);
free(c);
free(d);
free(d2);
free(e);
free(f);
free(g);
return 0;
}
bp는 free(g) 직후에만 걸어주자.
1. fastbin[0] : 0x20 size의 free chunk 하나가 binlist에 추가되었다.
2. fastbin[1] : 0x20과 0x25로 할당되었던 chunk는 최종적으로 0x30으로 할당되었고
fast bin은 LIFO 구조이므로 먼저 free된 b chunk(0x602020)이 먼저 들어갔고,
그 다음으로 free된 0x30byte free chunk인 b2(0x602050)이 다음으로 들어간 것을 알 수 있다.
3. fastbin[2] : 0x40byte free chunk 추가
4. fastbin[3] : free chunk d와 d2가 추가되었다.
.
.
.
계속해서 똑같은 방식으로 fastbin에 추가된다.
지금 fastbin에 이렇게 free chunk가 이와같은 식으로 추가되어있다.
a, c, e, f, g chunk는 next free chunk를 가리키는 포인터가 저장되어있는 fd는 0으로 설정되어 있다.
그 이유는 현재 free chunk가 아무것도 없는 상태에서 0x20 size의 chunk가 사용중이라고 생각해보면
0x20 size의 allocated chunk의 memo 영역에는 사용자가 입력한 데이터가 들어가있을것이다.
0x20 size의 chunk가 free 되면 fastbin[0]에 들어가는데, fd가 0으로 초기화 되지 않는다면
fastbin[0] -> 0x20 chunk -> 0x20 chunk's mem
이렇게 리스트가 연결되고 다음에 동일한 size인 0x20 chunk가 malloc 요청이 들어왔을때
fastbin[0]에 있는 0x20 chunk를 반환하는 것이 아닌 그 chunk의 mem을 반환할려하기 때문이다.
그래서 실제로 b chunk만 살펴봤을떄 fd는 0으로 바뀐것을 볼 수 있다.
다른 chunk들은 보지 않았지만 fastbin에 처음 들어간
free chunk들의 fd 값도 0일거다.
그리고 fastbin에서는 free chunk들은 병합하지 않기 때문에 prev_inuse bit가 변하지 않는다.
하지만 fastbin도 절대 병합하지 않는것이 아니라 가끔 병합을 하기도 한다.
만약 fast chunk 사이즈 이상의 chunk를 free 하려고 할때 병합이 되면서
unsorted bin으로 들어간다.
결론적으로 이렇게 fastbin들은 병합 과정을 거치지 않기 때문에 fd만 필요하고
bk가 필요없는 단일연결리스트로 구성된다.
이러한 특징 때문에 작은 사이즈의 chunk들의 할당 및 해제가 빠르게 이루어지지만
internal fragmentation을 발생시킬 수도 있다.
3. Unsorted bin
초반에 말했던 bins의 첫번째 인덱스가 지금 나오는 unsorted bin의 list로 사용된다.
fast chunk를 제외한 다른 size의 chunk들이 free 될 때는 먼저 unsorted bin으로 들어간다.
그 이후 malloc 요청 시 동일한 크기의 영역을 다시 요청하는 경우 unsorted bin에 들어있는
chunk를 바로 재사용할 수 있게 한다.
unsorted bin은 fastbin과 달리 FIFO 방식으로 동작하며, malloc 요청으로 unsorted bin에서
검색된 chunk들은 알맞은 size인 경우 재사용을 하고 알맞은 사이즈가 아닌 경우
각자 자기의 size에 맞는 bin으로 돌아가게 된다.
이게 무슨 소리냐면 unsorted bin의 경우 단 한번의 재사용 기회만 주어진다.
이제 unsorted bin의 특징에 대해서 알아보자
1. unsorted bin은 1개의 bin만 사용
2. 이중 연결리스트로 구성
3. small, large chunk를 보관
4. 다양한 크기의 chunk가 unsorted bin에 저장될 수 있다.
5. fast chunk를 제외한 다른 chunk가 free되면 unsorted bin에 보관 및 재사용
6. FIFO 방식
7. 검색된 chunk는 재할당되거나 실패하면 원래의 bin으로 돌아감
8. unsorted chunk는 NON_MAIN_ARENA(A) flag를 절대 셋팅하지 않음
코드로 디버깅해보면서 unsorted bin에 대해서 알아보자
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int main()
{
char* a=(char*)malloc(0x20);
char* a2=(char*)malloc(0x100); // small chunk
char* b=(char*)malloc(0x14);
char* b2=(char*)malloc(0x111); // small chunk
char* c=(char*)malloc(0x30);
char* c2=(char*)malloc(0x122); // small chunk
char* d=(char*)malloc(0x24);
char* e=(char*)malloc(0x22);
free(b); // insert fastbin
free(d); // insert fastbin
free(a2); // insert unsorted bin
free(b2); // insert unsorted bin
free(c2); // insert unsorted bin
char* f=(char*)malloc(0x100);
char* g=(char*)malloc(0x110);
free(g);
return 0;
}
free(d)까지 bp걸고 실행해보자
총 8개의 chunk가 할당되었고 지금 free된 chunk인 b와 d는
fast chunk이므로 unsorted bin으로 들어가지 않았고
fastbin으로 들어간것을 볼 수 있다.
지금은 free(c2)까지 bp 걸고 돌린 상황이다.
a2, b2, c2는 small chunk이므로 free하면 unsorted bin에 들어갔다가 small bin에 들어갈것이다.
unsorted bin에 a2, b2, c2가 이중 연결 리스트로 연결되어 있다.
unsorted bin은 FIFO 구조이므로 malloc 요청이 들어오면 unsorted bin에서 뒤져서
적절한 size가 있다면 제일 오른쪽부터 탐색할것이다.
만약 요청이 들어온 size가 0x100이라면 0x110 chunk를 바로 할당해줄 것이다.
하지만 들어온 요청 사이즈가 0x120이면 0x130을 할당해줘야 하므로
제일 왼쪽에 있는 0x130 size의 chunk(0x6022c0)을 할당해줘야 한다.
그럼 0x110 size는 탈락, 0x120 사이즈도 탈락하므로
이 두개의 chunk는 즉시 small bin으로 빠진다.
그래서 지금 다시 0x100을 할당해주는 경우를 보는데
unsorted bin에서 0x110 free chunk가 빠진것을 볼 수 있다.
그럼 0x130 chunk를 요청한 직후를 살펴보자.
...
free(b);
free(d);
free(a2); // 0x100
free(b2); // 0x110
free(c2); // 0x122
char* sx=(char*)malloc(0x130);
...
그냥 위에 코드에서 살짝 수정했다.
header 포함 0x140이 할당이 되었고
unsorted bin에서 원하는 size를 찾지 못해서 unsorted bin에 있던
free chunk들은 small bin에 들어갔다.
그래서 우리는 unsorted bin에서는 FIFO 구조를 가지고 있어 한번이라도 탐색을 진행한
free chunk는 각자 자신의 size에 맞는 bin으로 들어가는것을 알 수 있다.
근데 한가지 신기한게 있다.
무슨 상황이냐면 현재 0x20 size의 chunk가 free되어서 fastbin에 들어가 있는 상황이다.
근데 0x100 size의 chunk가 free 되어서 unsorted bin에 들어갔다.
unsorted bin에서는 물리적으로 인접한 free chunk들은 병합이 이루어진다.
그러면 0x100 size의 small chunk가 해제될 때 다음 chunk의 prev_inuse bit를 0으로 변경하긴 하지만
0x20 size의 free chunk는 fast bin에서 관리되는 특징때문에 그 다음 chunk의 prev_inuse bit가 현재
그대로 1로 셋팅되어 있을 것이다.
따라서 0x100 small chunk가 free 될때 0x20 chunk의 다음 chunk의 prev_inuse bit를 확인하고,
현재 1로 셋팅되어 있으므로 병합은 진행하지 않고 단순 자기 자신의 다음 chunk(0x20)의 prev_inuse bit만
0으로 변경한다. 이것도 소스코드에서 확인할 수 있다.
어쨌든 결론적으로 small chunk or large chunk size의 해제시 병합할 수 있는 chunk들은
병합을 하고 unsorted bin으로 들어간다.
추가적으로 한 코드만 더 살펴보자면
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int main(void){
char *a = (char *)malloc(0x110);
char *temp = (char *)malloc(0x20);
free(a); //insert into unsorted bin
char *b = (char *)malloc(0x80);
return 0;
}free(a) 직후를 bp 걸고 살펴보자
a가 unsorted bin에 들어갔다. 근데 만약에 unsorted bin에 들어있는 free chunk보다
더 작은 size를 요청하는 경우는 어떻게 될까?
지금 header 포함 0x90만큼의 chunk를 할당하였을때
unsorted bin에 있던 0x120의 chunk에서 0x90만큼 재할당해주고 남은 0x90은 last_reminder에 들어가게 된다.
unsorted bin도 여기서 끝!
4. small bin
small bin은 내용이 그리 많지 않다.
우선 small bin은 small chunk들이 free될 때 들어가는 곳이다.
그럼 small chunk의 기준을 알아보자
소스코드에서 smallbin range를 확인할 수 있는데, 만약 size가 MIN_LARGE_SIZE보다 작으면 small bin으로 구별된다.
MIN_LARGE_SIZE는 (NSMALLBINS - SMALLBIN_CORRECTION) * SMALLBIN_WIDTH이다.
MALLOC_ALIGNMENT는 16이고, SIZE_SZ는 8이다.
그러면 SMALLBIN_WIDTH는 16이고, SMALLBIN_CORRECTION은 0이 되므로
MIN_LARGE_SIZE는 1024가 된다.
즉 chunk의 최소 사이즈 0x20 ~ 0x400미만으로는 small bin으로 들어가지만 하지만 보편적으로는
0x80까지는 fastbin에 들어간다. 신기하게도 리스트에 연결된 chunk가 10개가 넘어가는 경우에는
0x20 ~ 0x80 size의 chunk가 small bin으로 들어간다고 한다.
좀 정리를 해보면
0x20 ~ 0x80 size chunk -> fastbin
리스트에 연결된 chunk(0x20 ~ 0x80) > 10 -> smallbin
이렇게 된다.
이제 small bin의 특징을 알아보자
1. FIFO 방식 사용
2. 62개의 bin 사용
3. 해제된 small chunk를 보관
4. 이중 연결 리스트로 구성
5. 0x20 ~ 0x400미만의 chunk를 관리
6. small bin에는 2개의 free chunk가 인접 불가능
7. 서로 인접한 경우 PREV_INUSE bit가 clear되므로 free할 때 인접한 free chunk와 병합
이제 코드로 디버깅하면서 smallbin 구조를 파악하자
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int main()
{
char* a=(char*)malloc(0x80);
char* b=(char*)malloc(0x400);
char* c=(char*)malloc(0x40);
char* d=(char*)malloc(0x3e0);
free(a);
char* e=(char*)malloc(0x500);
free(d);
char* f=(char*)malloc(0x500);
return 0;
}
지금 현재 A를 할당한 상태이다, header 포함 0x90만큼 할당이 되어서 small chunk에 해당한다.
그 다음 a를 free 한 직후로 가보자
A는 fast chunk가 아니므로 unsorted bin으로 우선 들어갔다
그 다음 e를 malloc한 직후까지 가보자
그럼 chunk a가 smallbin[7]로 들어온 것을 볼 수 있다.
그 다음 free(d)까지 가보자
그러면 unsorted bin에 들어온다. 마지막으로 f 할당 직후까지 가보면
smallbin[61]에 잘 적재되어 있는 것을 볼 수 있다.
smallbin은 쉬우니 여기서 끝!
5. Large Bin
large bin은 0x400 이상의 chunk가 지정되는 bin으로서, 메모리 할당가 반환의 속도가
앞에서 나온 bin들 중에서 가장 느리다.
bin의 개수는 63개이며 large bin은 다른 bin들과 다르게 각 인덱스에 연결되어 있는
chunk들의 사이즈가 동일하지 않다.
large bin의 특징을 살펴보자
1. 16개의 bin은 각 512byte 크기를 가지는 chunk의 binlist를 가진다.
2. 8개의 bin은 각 4,096byte 크기를 가지는 chunk의 binlist를 가진다.
3. 4개의 bin은 각 32,768byte 크기를 가지는 chunk의 binlist를 가진다.
4. 2개의 bin은 각 262,144byte 크기를 가지는 chunk의 binlist를 가진다.
5. 1개의 bin은 남은 크기를 가지는 chunk의 binlist를 가진다.
large bin은 bin 구성시 조금 특이한 성질을 가진다.
1. 각 bin들이 동일한 크기의 chunk만을 포함하지 않는다. 동일크기의 chunk도 존재하고 다른 크기의 chunk도 존재한다.
= 즉 해당 index가 나타내는 크기보다 작은 크기의 chunk들도 모두 포함된다.
2. 인접한 free chunk들은 병합을 한다.
1번이 조금 이해가 안갈 수 있는데 예를 들어 설명하자면
4k 크기를 위한 bin이 있다면 4096 byte의 chunk만 포함하는게 아니라
4088, 4000, 3989 등의 크기를 가지는 청크들도 포함한다.
얘네들은 할당의 효율성을 높이기 위해 크기 별로 정렬되는데, 이때 fd_nextsize, bk_nextsize가 이용된다.동일한 크기의 chunk는 fd_nextsize와 bk_nextsize가 연결이 되지 않는다.
그리고 무조건적으로 큰 size의 chunk가 다 largebin에 들어가는것이 아니라, 128kb 이상의 큰 size 요청은mmap syscall()을 이용하여서 별도의 메모리 영역을 할당해준다.
해당 크기의 chunk는 bin에 속하지 않으며, IS_MMAPED 플래그가 설정된다.
이제 코드로 디버깅하면서 large bin구조에 대해서 알아보자
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int main()
{
char* a0=(char*)malloc(0x3f0);
char* b0=(char*)malloc(0x80);
char* a1=(char*)malloc(0x400);
char* b1=(char*)malloc(0x40);
char* a2=(char*)malloc(0x410);
char* b2=(char*)malloc(0x200);
char* a3=(char*)malloc(0x420);
char* b3=(char*)malloc(0x200);
char* a4=(char*)malloc(0x430);
char* b4=(char*)malloc(0x300);
char* a5=(char*)malloc(0x440);
char* b5=(char*)malloc(0x300);
char* a6=(char*)malloc(0x450);
char* b6=(char*)malloc(0x300);
char* a7=(char*)malloc(0x460);
char* b7=(char*)malloc(0x300);
char* a8=(char*)malloc(0x470);
char* b8=(char*)malloc(0x300);
free(a0);
char* e0=(char*)malloc(0x500);
free(a1);
char* e1=(char*)malloc(0x500);
free(a2);
char* e2=(char*)malloc(0x500);
free(a3);
char* e3=(char*)malloc(0x600);
free(a4);
char* e4=(char*)malloc(0x600);
free(a5);
char* e5=(char*)malloc(0x500);
free(a6);
char* e6=(char*)malloc(0x500);
free(a7);
char* e7=(char*)malloc(0x600);
free(a8);
char* e8=(char*)malloc(0x600);
return 0;
}맨 마지막 malloc이 호출된 직후를 살펴보자
위에서 설명한 대로 동일한 size의 chunk들이 연결되는 것이 아닌것을 볼 수 있고,
정렬이 되어서 맨 왼쪽이 가장 큰 사이즈를 갖는다.
large bin도 끝!
6. Top Chunk
마지막으로 Top Chunk인데 Top Chunk는 간단하게만 살펴보고 끝내자
Top chunk는 arena 메모리 끝 부분에 위치한 chunk를 뜻한다. 이는 어떠한 bin에도 속하지 않으며
다음과 같은 상황에서 Top Chunk를 활용한다.
1. 사용자가 요청한 size가 어느 bin에서도 찾을 수 없을 때
= Top chunk에서 분할하여 할당
2. 사용자가 요청한 size가 어느 bin에서도 찾을 수 없고, top chunk size보다 커서 분할할 수 없을 때
※ top chunk < 요청 size < 128kb인 경우에는 main_arena = sbrk syscall로 확장, thread_arena = mmap으로 확장
※ top chunk < 128kb < 요청 size인 경우는 main_arena, thread_arena 모두 mmap으로 확장
References
https://wogh8732.tistory.com/180?category=699165
https://tribal1012.tistory.com/141
https://www.lazenca.net/pages/viewpage.action?pageId=1147929#id-01.Malloc-glibc(ptmalloc2)-Largebin
'Heap' 카테고리의 다른 글
| Structure of Chunk (0) | 2021.10.16 |
|---|---|
| Dynamic memory allocator (glibc malloc) (0) | 2021.10.15 |