malloc 함수 분석

본 게시물은 malloc 함수에 대한 간략한 설명을 하는 곳입니다. 기초적인 heap 지식이 있다는 가정하에 작성되었습니다. 

(자세한 주석과 코드 분석글은 별도로 올라갈 예정입니다)

먼저 malloc 의 작동과정을 알기 이전에 arena에 대해서 간략하게 정리하겠다. 

Arena 

 우리는 main arena에 대해서는 자주 들어보았을 것 이다. arena는 heap영역을 관리하는 영역이다(fastbin, smallbin, largebin, topchunk 등등..). 멀티스레드 환경에서 heap을 관리하기 편하기 위해 만들어졌다(동기화 문제등). 그러나 스레드당 arena 가 하나씩 할당되는 것은 아니고 cpu의 물리코어 개수에 비례해서 최대 수가 정해져 있으며, 최대로 할당가능한 arena수가 넘어서게 되면 arena를 재사용하게 된다. 

 main arena는 프로그램이 실행되는 메인스레드가 사용하는 아레나이다. 만약에 새롭게 스레드를 만들어 그 스레드에서 malloc을 사용한다면 새롭게 아레나가 생기고, 기존에 이용하던 heap영역이 아닌 새로운 영역을 할당받아 이용하게 될 것 이다. 

arena들은 새로 생성이 되면 구조체 변수를 통해 연결리스트로 관리된다. (main arena 부터 시작된다.)

 

__libc_malloc

stdlib.h 의 malloc() 함수를 호출하게 되면 먼저 호출되는 함수는 void *__libc_malloc(size_t bytes) 함수이다.

__libc_malloc은 먼저 __malloc_hook 전역변수에 값이 있는지 검사를 한다. 그리고 해당 hook 값으로 점프한다. 

 void *(*hook) (size_t, const void *) 
    = atomic_forced_read (__malloc_hook);//__malloc_hook 값을 읽어오기 
  if (__builtin_expect (hook != NULL, 0)) 
    return (*hook)(bytes, RETURN_ADDRESS (0)); //jmp __malloc_hook

 그리고 만약 gblic 버전 2.26 이상이여서 tcache를 사용한다면 tcache에서 사용할 수 있는 청크가 있는지 검사를 하고 해당 사이즈의 tcache를 검사하여 만약 청크가 있다면 반환해준다. 이 과정에서 fastbin과는 다르게 청크의 사이즈 검사가 없다 . 별다른 과정이 없기때문에 매우 빠르다. 

 if (tc_idx < mp_.tcache_bins //요청사이즈가 tcache 사이즈에 포함될시에
      && tcache //그리고 tcache가 init 되었을 때에 
      && tcache->entries[tc_idx] != NULL) //그리고 해당 사이즈의 bin에 청크가 존재할시
    {
      return tcache_get (tc_idx); //tcache bin에서 할당받는다 
    }

만약 tcache에서 사용가능한 청크가 없었으면 싱글스레드인지 멀티스레드인지 확인을 한다. 그 뒤 해당 스레드에 arena를 할당하거나, 이미 할당된 arena를가지고 와서 _int_malloc 함수에 arena 와 size를 인자로 넘겨주고 _int_malloc 함수의 반환 값을 반환해준다. 

 

__malloc_hook

 한가지 간과할 수 있는 사실인데, __malloc_hook은 단순한 디버깅 용도가 아니다. 이 전역변수는 처음에 malloc_hook_ini라는 함수의 주소를 가지고 있어서 처음  malloc을 실행하면 해당 함수가 실행된다. malloc_hook_ini는 __malloc_hook 을 NULL로 설정해주고 ptmalloc_init 함수를 실행해준 뒤 다시 __libc_malloc을 호출해준다. 

ptmalloc_init

 malloc.c 에는 thread_arena 라는 thread 전역변수가 존재한다. 각 스레드 별로 가지는 arena를 나타내는데,  메인스레드의 thread_arena를 &main_arena로 설정해주고, 이 main_arena의 값들(unsorted bin, smallbin 청크들의 fd bk 등) 을 초기값으로 세팅해주는 것이 이 함수이다. 

Tcache 

먼저 살펴볼 것은 tcache 이다. tcache의 주요함수는 크게 tcache_init , tcache_get, tcache_put 이다. 

• tcache init

 현재 arena의 힙 공간에서 공간을 받아와서 tcache arena를 생성해준다. 스레드 전역변수인 tcache가 tcache arena의 주소를 관리한다. 

 

•  tcache_get

해당 인덱스의 tcache bin 에서 청크를 반환한다. 그리고 libc 2.29 부터 tcache 로 들어간 청크는 bk 에 tcache arena의 주소가 담겨있는데 이 부분도 0으로 설정해서 반환한다. 

 

•  tcache_put

해당 인덱스의 tcache에 해당 청크를 집어넣는다.

 

 

밑의 글들의 순서는 실제 _int_malloc 함수의 알고리즘 순서와 동일하다.

Fastbin 에서 청크 가지고 오기

 fastbin은 fd로만 이루어진 리스트이다. 따라서 청크를 가지고 올때 top에 있는 청크를 반환해주고 반환된 청크의 fd를 top으로 설정해주는 작업이 fastbin에서 청크를 가져오는 방법이다. 할당 받은 후 해당 사이즈의 tcache가 비어있는지 확인을 하고 , tcache에 넣을 수 있는 만큼 fastbin에서 tcache로 옮긴다. 

 

Smallbin 에서 청크 가지고 오기

 smallbin은 fd,bk로 이루어진 이중연결리스트이다. 따라서 bk로 탐색을 한다는 것을 제외하면 fastbin 과 코드적으로 다른 것은 크게 없다. 추가적으로 smallbin 부터는 free된 청크의 다음청크의 prev_inuse bit 가 이용되기 때문에 할당될 때 다음청크의 inuse bit를 1로 설정해주는 과정이 추가된다. 할당 이후에는 남아있는 청크들을 tcache로 옮길 수 있으면 옮긴다. 

 

Unsortedbin 에서 청크 가지고 오기

 unsortedbin에서 청크를 탐색한다. 한사이클 돌아서 모든 청크를 확인하거나 카운트가 1만이상이 되면 종료한다.  

이후 아래의 과정을 수행한다. 

 

1. unsortedbin에 청크가 하나가 있고, 그 청크가 last_remainder 이며, 할당요청한 사이즈+0x20보다 클 경우  

해당청크를 반환하고 분할하여 남은 부분은 last_remainder로 설정하고 다시 unsortedbin에 넣어준다. 

 

2. 할당요청한 사이즈와 unsortedbin의 청크 크기가 동일할경우 

 tcache를 사용하면 tcache에 해당청크를 넣어주고, return_cached를 1로 설정한다. tcache를 사용하지 않으면 해당 청크를 바로 반환한다. 

 

3. 1,2 번 과정에서 반환이 되지 않았다는 것은 재할당 기회를 잃은 것이니 smallbin 또는 largebin으로 해당 청크를 넣어준다. 

 

smallbin의 경우에는 별다른 특징이 없지만 largebin은 정렬된 상태로 유지가 되야 하기 때문에 특별한 과정이 추가된다. 바로 fd_nextsize 와 bk_nextsize 를 설정하는 것. largebin은 생소할 수 있으니 잠깐 정리를 하고 가자. 

---

 

Largebin 특징 

 

largebin이 관리하는 사이즈 : 0x400 이상의 요청부터 관리한다

 

largebin[0] ~ largebin[31] (32개) : 0x40(64) bytes씩 증가

largebin[32] ~ largebin[47] (16개) : 0x200(512) bytes씩 증가

largebin[48] ~ largebin[55] (8개) : 0x1000(4,096) bytes씩 증가

largebin[56] ~ largebin[59] (4개) : 0x8000(32,768) bytes씩 증가

largebin[60] ~ largebin[61] (2개) : 0x40000(262,144) bytes씩 증가

largebin[61] (1개) : 이외의 남은 크기

 

smallbin, unsortedbin 과 다르게 fd를 통해서 탐색 한다. 

 

FIFO 구조로, 항상 정렬된 상태를 유지하며 bin->fd에 가장 큰 청크, bin->bk에 가장 작은 청크가 존재한다. 또한 fd_nextsize , bk_nextsize는 크기가 동일한 청크 사이에서는 사용되지 않는다. 이를 그림으로 표현하면 아래와 같다. 

 

직접그림

---

4. 2번에서 설정한 return_cached가 1일시

tcache에서 해당 사이즈의 청크를 할당 받는다.

 

Largebin에서 청크 가지고 오기

largebin에서 요청한 사이즈와 가장 사이즈가 비슷한 청크를 할당받는데, 아래의 루틴에 따라서 할당이 된다. 

 

1. 해당 청크의 사이즈가 요청한 사이즈+0x20 보다 클 때 

unsortedbin 처럼 분할한 뒤 unsortedbin->fd (맨 처음 부분) 에 넣어준다.

 

2. 아닐 때 

그냥 통째로 반환한다. fd_nextsize, bk_nextsize 는 NULL로 설정해준다.

 

이후 해당 청크를 리스트에서 unlink 시켜준다. (unlink 함수를 사용하는 건 아님)

Binmap 에서 탐색하기 

Binmap은 bin이 청크를 가지고 있는 유무를 알려준다. 64bit 환경에서 binmap은 배열원소가 4개이다. 

arena헤더에 선언된 bins 배열의 인덱스 기준으로 

0x00~0x20번째 bin은 binmap[0], 0x20~0x40번째 bin은 binmap[1] , 0x40~0x60번째 bin은 binmap[2], 나머지 bin은 binmap[3]에 기록된다. 

binmap은 smallbin 또는 largebin에 청크가 들어갈 때 세팅된다. 

세팅은 mark_bin 이라는 매크로 함수를 통해서 이루어지는데, 세팅될때 arena_header에 있는 bins 에서 해당 bin의 인덱스를 가지고 세팅이 된다. 예를 들어보자. 

 

현재 0x130 사이즈의 청크가 smallbin에 들어갔고, binmap[0]=0x80000 으로 세팅되었다. 

0x80000을 이진수로 표현하면 1000 0000 0000 0000 0000 이다. 실제로 arena_header에서 첫번째 bin은 unsortedbin 이고 저 binmap 에서 마지막 비트는 사용되지 않기 때문에 마지막 비트 2개를 제외하면 

10 0000 0000 0000 0000 이 되고 자리수를 세어보면 18로 smallbin[17] 과 동일한 의미라는 것을 알 수 있다. 

(위 그림 참조)

 

 

binmap을 탐색하면서 가장 작은 청크 부터 큰 청크 순서대로 탐색한다. 그리고 선택한 청크에 대해 다음 과정을 수행한다. 

 

1. 해당 청크의 사이즈가 요청한 사이즈+0x20 보다 클 때 

unsortedbin 처럼 분할한 뒤 unsortedbin->fd (맨 처음 부분) 에 넣어준다. 이때  요청한 사이즈가 smallbin 범위라면 last_remainder는 분할된 청크로 설정된다.

 

 

2. 아닐 때 

그냥 통째로 반환한다. 

(unsortedbin에 0x30 사이즈 청크가 있을 때 0x20(헤더포함) 요청하면 0x30사이즈 청크가 반환되는 것이 이 경우)

 

3. 다 탐색했을 때

 아래의 topchunk에서 할당받기로 이동한다. (goto)

Topchunk에서 할당받기 

이제 모든 bin을 다 순회했고, 할당을 받을 곳이 없다고 판단되어 topchunk에서 할당을 받아야 한다.

 

1. topchunk 크기가 충분할 경우

topchunk를 분할해서 준다. 

 

2. 충분하지 않은데, fastbin에 청크가 있는 경우 

malloc_consolidate 함수를 실행시켜 fastbin에 있는 청크를 unsortedbin으로 옮기는 작업을 수행, 병합할 청크들을 다 병합하고 binmap에서 탐색하는 과정으로 다시 간다.

 

3. 진짜 공간이 없는경우 

sysmalloc함수를 이용해서 할당받는다. 

Sysmalloc으로 mmap 할당받기

 sysmalloc 함수는 sbrk 와 mmap 시스템 콜을 사용해서 공간을 할당한다. 

처음 main_arena에서 heap 공간을 할당받는 경우에는 sbrk 를 이용해서 할당을 받는다. 매우 큰 사이즈를 요청하는 경우에는 mmap으로 할당받고 , 그렇지 않다면 할당된 heap 공간이 확장되어 그 공간에서 할당을 받는다. 

(정확히는 sbrk가 실패하고 mmap이 실행됨 )자세한 코드 분석 이후 업데이트 할 예정. 

 

코드 분석하느라 힘들었따.. sysmalloc은 좀 난해한 부분이 있어서 걸릴지도..