heap(3) - glibc malloc(2) (feat. chunk)

참고 : GNU C Library의 Memory Allocator인 ptmalloc2(glibc 2.23)를 대상으로 설명

 

지금부터는 실제로 메모리 할당 및 해제되는 공간인 청크에 관한 이야기를 시작하도록 하겠다.

중간중간에 bins에 대한 내용이 언급되는데 여기서는 그냥 free된 청크를 관리하는 정도로만 알고 넘어가자

 

---

1. Chunk

1.1 Chunk란?

• malloc()에 의해 메모리 할당 요청이 들어온 경우 실제로 할당받는 영역

• 실제로 저장되는 data와 메타 데이터가 저장된 header까지 포함

• 청크의 크기 : 2*sizeof(size_t) 의 배수로 할당

  • 청크의 최소 크기 : 4*sizeof(void*)

  • 32bit system : 8bytes 배수로 할당

  • 64bit system : 16bytes 배수로 할당

• Chunk의 종류 : Allocated chunk, Free chunk, Top chunk

종류는 총 3가지이지만 동일한 구조체를 사용하므로 동일한 구조를 갖는다.

다음 소스 코드를 통해 Chunk의 구조를 확인해보자

 

1.2 Chunk 구조

1) malloc_chunk 구조체

struct malloc_chunk {

  INTERNAL_SIZE_T      prev_size;  /* Size of previous chunk (if free).  */
  INTERNAL_SIZE_T      size;       /* Size in bytes, including overhead. */

  struct malloc_chunk* fd;         /* double links -- used only if free. */
  struct malloc_chunk* bk;

  /* Only used for large blocks: pointer to next larger size.  */
  struct malloc_chunk* fd_nextsize; /* double links -- used only if free. */
  struct malloc_chunk* bk_nextsize;
};

[https://elixir.bootlin.com/glibc/glibc-2.23/source/malloc/malloc.c#L1111]

 

2) 설명

• prev_size : 인접한 이전 청크의 크기

  • 인접한 청크가 free된 경우 : free된 청크의 사이즈 값으로 초기화

  • 인접한 청크가 allocated인 경우 : 0으로 세팅됨

• size : 현재 할당된 청크의 크기이며 32bit, 64bit에서 8bytes, 16bytes단위로 할당되므로 마지막 3bit는 flag로 사용

  • NON_MAIN_ARENA [A] (0x4) : Main Arena가 아닌 Arena로부터 할당받은 경우 1로 세팅, 해당 플래그가 설정된 경우 Allocator는 모든 Arena를 검색하여 해당 Arena의 하위 힙 내에 청크가 존재하는지 확인해야 하지만 설정되지 않은 경우 Allocator는 Main Arena에서 나온 것을 알기 때문에 탐색 시간을 단축할 수 있음

  • IS_MMAPPED [M] (0X2) : Chunk가 mmap()으로 할당받은 경우 1로 세팅, free될 경우 Allocator는 해당 청크가 사용하고 있는 영역(mmap()으로 할당받은 메모리 영역)을 mummap()을 통해 바로 커널에게 돌려주는데 사용

  • PREV_INUSE [P] (0X1) : 인접한 이전 청크가 사용중(할당)인 경우 또는 free된 청크가 fastbins에 들어가는 경우 1로 세팅, 해당 플래그가 0x0으로 세팅된 경우 인접한 이전 청크와 안전하게 결합하여 훨씬 큰 청크를 만드는데 사용

• fd(forward pointer), bk(backward pointer) : 청크가 free된 경우 세팅되며 free된 청크를 가리키는 포인터(free된 청크는 bins들에 의해 관리됨)

• fd_nextsize, bk_nextsize : 청크들은 비슷한 크기로 묶어서 관리하기 때문에 가장 큰(512bytes보다 큰, large bin)청크가 free된 경우 세팅됨

 

---

2. Chunk의 종류

2.1 Allocated Chunk

1) Allocated Chunk

Allocator에 의해 메모리 할당을 받아서 현재 사용중인 Chunk

 

 

2) Structure of Allocated Chunk

 

3) Example

3-1) Allocated.c

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<unistd.h>

void* thread_func(void*);

int main(){
	
	char *p1 = (char*)malloc(1);
	char *p2 = (char*)malloc(2);
	char *p3 = (char*)malloc(33);
	char *p4 = (char*)malloc(34);
	int t_id, status;
	pthread_t t1;
	
	if(pthread_create(&t1, NULL, thread_func, NULL))
		printf("Thread Creation Error\n");
	
	if(pthread_join(t1, (void**)&status))
		printf("Thread Join Error\n");
	
	strncpy(p1, "AAAA", 4);
	strncpy(p2, "BBBB", 4);
	strncpy(p3, "CCCC", 4);
	strncpy(p4, "DDDD", 4);
	
	
	free(p1);
	free(p2);
	free(p3);
	free(p4);

	return 0;
}
	
	
void* thread_func(void *data){
	
	pid_t pid;
	pthread_t tid;
	
	char *p1 = (char*)malloc(10);
	char *p2 = (char*)malloc(10);
	
	pid = getpid();
	tid = pthread_self();
	
	printf("Creation Thread!!\n");
	printf("pid : %u, tid : %x\n", (unsigned int)pid, (unsigned int)tid);
	
	free(p1);
	free(p2);
}

• 위 코드에서 주의할 부분은 p1, p2가 각각 1byte, 2byte할당을 하였지만 strncpy함수를 통해 1byte, 2byte보다 더 큰 값을 저장하는 것이다.

3-2) Debugging

[p1, p2에 메모리 할당]

• 힙 영역이 생성된 것을 확인

• 두 개의 청크가 생성되었으며 size값이 0x20(32)인 것을 확인

• 1byte, 2byte 메모리 할당을 요청하였으나 청크의 최소 크기가 4*sizeof(void)이므로 0x20(32)bytes만큼 할당

 

[p3, p4에 메모리 할당]

• 두 개의 청크가 더 생성되었으며 size값이 0x30(48)인 것을 확인

• p3, p4에 33bytes, 34bytes크기를 요청하였으나 이보다 더 큰 0x30(48)bytes만큼 메모리 할당

• 현재 시스템이 64bit 환경이므로 청크의 최소 크기인 0x20(32)bytes에서 16bytes배수로 메모리 할당이 되므로 0x30(48)bytes만큼 할당

 

[스레드 생성 후 malloc]

• 이후에 thread함수에서 malloc하는 2개의 청크가 생성

• 위에 main함수에서 호출한 청크의 flag가 다른 것을 확인

• 0x5(101)이므로 NON_MAIN_ARENA(0x4), PREV_INUSE(0x1)가 세팅된 것을 확인

 

[메인 함수에서 모든 청크 free된 직후]

• 4개의 청크가 free되며 fd값이 설정된 것을 확인할 수 있다.

• 앞서 말했듯이 bins는 비슷한 크기의 청크끼리 관리하므로 p1과 p2, p3와 p4끼리 linked list로 된 것을 확인할 수 있다.

• 또한, 모두 다 free되었음에도 4개의 청크 모두 fastbins에 들어가므로 flag값에 prev_inuse는 그대로 0x1로 세팅됨

(근데 마지막에 처음 보는 청크가 생기는데 저게 무엇을 의미하는지는 잘 모르겟음;;)

 

[추가]

밑에서 설명하겠지만 메모리 할당을 요청한 경우 Top Chunk에서 분할하여 할당하게 되는데 만일, Top Chunk의 사이즈보다 더 큰 메모리 할당을 요구하며 어떻게 될까?

 

+) 0x21000보다 큰 메모리 할당을 요청한 경우

• malloc()호출 시 mmap을 호출함

• 청크가 mmap을 통해 새로 할당되었으므로 flag값이 0x2로 세팅된 것을 확인

• 또한 힙 영역에 할당되는 것이아니라 mapped영역에 포함되는 것을 확인

 

 

2.2 Free Chunk

1) Free Chunk

Allocator에게 반환된 Chunk를 뜻하며 Allocated Chunk구조에서 Free Chunk구조로 변경되면서 Data부분에 fd, bk가 생김(추가로 크기가 큰 경우 fd_nextsize, bk_nextsize도 생김)

 

2) Structure of Free Chunk

 

• 여기서 마지막에 다음 청크의 헤더인 prev_size까지 포함된 것을 볼 수 있다.

• prev_size는 앞서 얘기했듯이 인접한(물리적으로 연속된 주소) 이전 청크가 free된 경우 세팅된다고 하였다.

• 따라서 다음 청크의 prev_size에는 이전 청크의 prev_size와 동일한 값을 가지며 이를 boundary tags라고 부른다.

• boundary tags를 통해 이전 chunk의 헤더 위치를 쉽게 찾을 수 있으므로(물리적으로 연속되어 있으므로 사이즈 값만으로 찾음) 이후에 chunk를 통합하는 경우 유용하게 사용된다. (단, fastbins의 경우에는 예외)

• 또한 flag값에서 PREV_INUSE가 0x0으로 세팅되는데 이는 fastbins인 경우 예외

 

3) Example

3-1) free.c

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

int main(){

	char *p1, *p2, *p3, *p4;
	
	p1 = (char*)malloc(500);
	p2 = (char*)malloc(600);
	p3 = (char*)malloc(700);
	p4 = (char*)malloc(800);

	printf("free chunk : p1, p3\n");
	
	free(p1);
	free(p3);

	printf("free chunk : p2, p4\n");
	
	free(p2);
	free(p4);
	
	return 0;
}

 

3-2) Debugging

[malloc 이후]

• 4개의 청크가 생성되며 fd와 bk는 아직 설정되지 않았다.

 

[p1 free 이후]

• fd, bk가 설정되어 있는 것을 확인할 수 있음

• 해당 영역은 메인 아레나에 위치

• fd, bk는 <main_arena+88>을 가리키며 <main_arena+88>은 Arena의 헤더 구조체인 malloc_state의 Top Chunk를 가리키는 포인터 멤버 변수이다.

 

[p2 free 이후]

• fd, bk가 free된 청크끼리 서로 가리키고 있음

• free되지 않은 청크들은 flag의 PREV_INUSE가 0x0으로 세팅됨(fatbins에 들어가지 않음)

 

[p3 free 이후]

• p1, p2, p3가 병합되어 free된 영역의 size값이 증가된 것을 확인

 

[p4 free 이후]

• 전부 다 병합된 것을 확인

 

 

2.3 Top Chunk

1) Top Chunk

• Arena의 가장 마지막에 위치하는 청크이며 새롭게 malloc을 호출하여 할당되면 Top Chunk에서 분리되어 청크를 할당한다. 만약 Top Chunk에 인접한 Chunk가 free되면 Top Chunk에 병합된다.

• Top Chunk가 분할되는 경우는 재사용 가능한 Free Chunk가 없거나(메모리 할당 요청을 만족하지 못하는) Top Chunk가 반환할 수 있는 크기가 존재하는 경우 다음과 같이 2개로 분할된다.

  • User Chunk : 사용자가 요청한 크기

  • Remainder Chunk : 요청한 크기의 나머지 부분으로 새롭게 Top Chunk가 됨

• 만일, Top Chunk의 크기보다 큰 사이즈를 요청한 경우

  • Main Arena : sbrk() 호출하여 메모리 확장하여 Top Chunk의 크기 늘림

  • Sub Arena : mmap() 호출하여 메모리 할당

2) Example

2-1) topchunk.c

#include<stdio.h>
#include<stdlib.h>

int main(){

        char *p1 = (char*)malloc(500);
        char *p2 = (char*)malloc(600);
        char *p3 = (char*)malloc(700);
        char *p4 = (char*)malloc(800);


        free(p1);
        free(p2);

        free(p4);
        free(p3);

        return 0;
}

 

2-2) Debugging

[malloc 호출 직전]

• Top Chunk 존재하지 않음

[p1 malloc() 호출 직후]

• Top Chunk의 위치는 0x602200이며 size값은 0x20e00이다.

• 이는 원래 Top Chunk의 크기가 0x21000이지만 0x200만큼의 메모리 할당요청이 들어오면 Top Chunk에서 분리되어 0x200만큼 Chunk가 생성되고 나머지(remainder chunk)인 0x20e00(0x21000 - 0x200)만큼 남게 되는 것이다.

• 하지만 실제로 Top Chunk에 저장된 값은 0x20e01인데 마지막 flag비트인 0x1이 세팅됨

 

[p2 malloc() 호출 직후]

• 이전 Top Chunk의 위치 : 0x602200

• 현재 할당된 Chunk의 위치 : 0x602200

• 현재 Top Chunk의 위치 : 0x602460

 

[p3 malloc() 호출 직후]

• 이전 Top Chunk의 위치 : 0x602460

• 현재 할당된 Chunk의 위치 : 0x602460

• 현재 Top Chunk의 위치 : 0x602730

 

[p4 malloc() 호출 직후]

• 이전 Top Chunk의 위치 : 0x602730

• 현재 할당된 Chunk의 위치 : 0x602730

• 현재 Top Chunk의 위치 : 0x602a60

 

[p1, p2 free호출 직후]

• p1과 p2가 서로 병합되어 Free Chunk를 이룸

• Top Chunk의 위치는 변함이 없음

 

[p4 free 호출 직후]

• Top Chunk와 가장 인접한 Chunk인 p4가 Free되자 Top Chunk와 결합된다.

• 이로써 Top Chunk의 위치는 원래 p4 Chunk의 위치인 0x602730으로 변하며 size값은 원래 0x205a0에서 p4의 size인 0x330을 더한 0x208d0으로 세팅됨

 

[p3 free 호출 직후]

• 모든 청크가 정리되고 Top Chunk도 원래대로 돌아온다.

• 모든 청크가 해제되도 heap영역은 사라지지 않는다.

 

 

---

3. 참고 자료

• https://wogh8732.tistory.com/179?category=699165

• https://www.lazenca.net/pages/viewpage.action?pageId=1147929#id-01.Malloc-glibc(ptmalloc2)-Structofmalloc_chunk

• https://www.youtube.com/watch?v=l0GVitgBPf0

• https://umbum.dev/386?category=761562