glibc Malloc

Glibc Malloc 

original source: http://studyfoss.egloos.com/5206979

malloc() 함수의 서비스 루틴은 public_mALLOc() 함수이며 실제로는 전처리 과정에 의해 __libc_malloc()이라는 이름으로 바뀐다. __malloc과 malloc은 이 함수에 대한 alias이다.) public_mALLOc() 함수는 다음과 같은 작업을 수행한다.

1. __malloc_hook이 정의되어 있다면 해당 hook을 호출한 후 종료한다.

2. 그렇지 않으면 malloc을 처리할 heap 영역(arena)를 찾는데 일반적으로 main_arena가 사용된다.

3. arena에 대한 lock을 건 후에 실제 malloc의 처리 루틴인 _int_malloc() 내부 함수를 호출한다.

4. 만약 _int_malloc() 함수가 NULL을 반환했다면 다른 arena에 대해 _int_malloc()을 다시 한 번 호출한다.

5. arena에 걸린 lock을 해제한다.

6. _int_malloc() 함수가 반환한 값을 반환하고 종료한다.

_int_malloc() 함수는 다음과 같은 작업을 수행한다.

Fast Bin Search

요청한 크기를 chunk 크기에 맞춘다. 즉, 헤더를 위한 4 바이트를 더한 후 8 바이트 단위로 정렬(align)한다. 이 후로는 chunk 크기를 기준으로 계산한다. 주어진 크기가 fast bin에 속한다면 (<= 72) fast bin 내의 free chunk를 찾아본다. 주어진 크기에 맞는 fast bin의 인덱스를 계산한다. 해당 인덱스의 포인터가 가리키는 chunk를 victim 지역 변수에 저장한다. victim이 NULL이 아니라면 fast bin의 해당 인덱스에 victim->fb가 가리키는 chunk를 저장하고 victim의 데이터 영역에 대한 포인터를 반환한다. (종료)

Small Bin Search

주어진 크기가 small bin에 속한다면 (< 512) small bin 내에서 free chunk를 찾아본다. 주어진 크기에 맞는 small bin의 인덱스를 계산하여 idx 지역 변수에 저장한다. 해당 인덱스 내에 가장 오래된 chunk를 victim 지역 변수에 저장한다. victim이 올바른 chunk를 가리킨다면 해당 인덱스 내의 리스트에서 victim을 제거하고, victim 바로 다음에 위치한 chunk의 헤더에 P (PREV_INUSE) 플래그를 설정한 뒤 victim의 데이터 영역에 대한 포인터를 반환한다. (종료) 

Large Bin Search

large bin은 바로 찾아보지 않고 다음과 같은 준비 과정을 거친다. 주어진 크기에 맞는 large bin의 인덱스를 계산하여 idx 지역 변수에 저장한다. 만약 fast bin을 포함하고 있다면 이들을 모두 병합(consolidate)하여 보다 큰 chunk로 만든다. 이는 큰 메모리 요청을 받은 경우에는 더 이상 작은 크기의 요청이 (최소한 당분간은) 없을 것이라고 가정하기 때문이다. (이로 인해 fast bin으로 인한 fragmentation 문제를 줄일 수 있다.) 이제 unsorted bin을 검색하여 일치하는 크기의 free chunk가 있는지 검색한다. unsorted bin 내의 가장 오래된 chunk를 victim 지역 변수에 저장한다. victim을 unsorted bin의 리스트에서 분리한다. victim의 크기와 주어진 크기가 일치한다면 victim을 반환한다. (종료)

Bin is not Found

idx 값을 하나 증가시킨 후 더 큰 크기의 bin 내에 free chunk가 있는지 검사한다. (이는 bitmap을 통해 빨리 확인할 수 있다.) 현재 인덱스에 해당하는 bitmap을 검사하여 free chunk가 있는지 확인한다. 만약 해당 bin이 비어있다면 인덱스를 하나 증가시킨 후 검사를 다시한다. bitmap이 설정된 bin이 있다면 해당 bin 내의 (가장 작은 크기의) 가장 오래된 chunk를 victim 지역 변수에 저장한다. victim을 리스트에서 분리한다. victim의 크기가 요청을 처리하고도 다른 chunk를 구성할 수 있을 정도로 크다면 분할하여 나머지 영역을 chunk로 만들어서 unsorted bin에 추가한다. 나머지 영역의 크기가 small bin에 속한다면 last_remainder 변수가 나머지 영역을 가리키도록 설정한다. victim을 반환한다. (종료)

Heap Increase

그래도 없다면 시스템의 heap 영역을 늘려야 한다. 이는 sYSMALLOc() 함수가 처리하며, 이 함수의 반환값을 반환하고 종료한다. sYSMALLOc() 함수는 다음과 같은 작업을 수행한다.

먼저 (1)요청된 크기가 mmap() 시스템 콜을 이용하도록 설정된 범위에 속하고 (>= 128K) mmap() 사용 횟수 제한을 넘지 않는다면 (< 65536회) mmap()을 호출한다. 호출이 성공하면 chunk에 M (IS_MMAPPED) 플래그를 설정하고 데이터 영역의 포인터를 반환한다. mmap()으로 할당한 chunk는 분할할 수 없으므로 크기에 여유가 있더라도 하나의 chunk로 사용된다.

그 보다 작은 크기거나 mmap() 호출이 실패했다면 heap 영역을 늘려야 한다. 증가시킬 크기는 요청한 크기에서 원래의 top chunk 크기를 빼고 top chunk가 기본적으로 가져야 할 여유 공간의 크기(pad)를 더한 후 할당 후 남은 영역에 chunk를 구성하기 위한 최소 크기(16)를 더한 값이다. 또한 이는 시스템의 페이지 크기에 맞춰 조정된다. (2)위에서 계산한 크기에 대해 sbrk() (MORCORE라는 이름을 사용한다) 시스템 콜을 호출한다. 호출이 성공했다면 __after_morecore_hook이 정의되어 있는지 검사하여 이를 호출한다. (3)호출이 실패했다면 크기와 횟수 제한에 상관없이 mmap() 시스템 콜을 호출하여 메모리 할당을 시도한다. 이것이 성공하면 해당 arena는 더 이상 연속된 주소 공간에 속하지 않으므로 NONCONTIGUOUS_BIT를 설정한다. 실패했다면 errno 변수를 ENOMEM으로 설정하고 NULL을 반환한다. (종료)