Internal functions

몇몇의 함수는 #define 지시문을 사용하여 정의해 놨기 때문에 호출된 파라미터는 함수종료 후에도 변경사항은 유지된다.

물론, MALLOC_DEBUG가 설정되지 않는 것으로 가정합니다.

arena_get (ar_ptr, size)

아레나를 획득하고 해당 뮤택스를 lock합니다. ar_ptr은 해당 아레나를 가르키는 포인터이고, size는 얼만큼의 메모리크기를 필요로 하는지를 나타낸다.

sysmalloc [TODO]

sysmalloc은 시스템에서 더 많은 메모리를 필요로 하는 malloc케이스를 처리한다. 입력시, av -> top에는 nb바이트에 대한 서비스 요청에 충분한 공간이 없으므로 av->top을 확장하거나 대체한다.

void alloc_perturb (char * p, size_t n)

perturb_byte (M_PERTURB를 사용하는 malloc의 변경가능한 매개 변수)가 0이 아닌 경우 (기본적으로 0), p가 가리키는 n 바이트를 perturb_byte ^ 0xff와 같게 설정합니다.

void free_perturb (char * p, size_t n)

perturb_byte (M_PERTURB를 사용하는 malloc의 변경가능 파라미터)가 0이 아닌 경우 (기본적으로 0), p가 가리키는 n 바이트를 perturb_byte와 동일하게 설정합니다.

void malloc_init_state (mstate av)

malloc_state 구조체를 초기화

이것은 malloc_consolidate 내에서만 호출되며, 어쨌든 동일한 컨텍스트에서 호출되어야합니다. 일부 최적화 컴파일러가 모든 호출 지점에서 인라인하려고 시도하기 때문에 malloc_consolidate 외부에서 직접 호출되지 않습니다. 이는 최적화가 아닐 수도 있습니다. (malloc_consolidate을 통해 인라이닝하는 것은 fine.)

fastbin이 아닌경우, 각 bin에 대해서 빈 순환 링크트리스트를 만든다.

av에 FASTCHUNKS_BIT 플래그를 설정한다.

av -> top을 첫 번째 unsorted chunk 로 초기화 한다.

unlink(AV, P, BK, FD)

bin에서 chunk를 제거하기 위해 정의된 매크로

제거하려는 청크의 크기가 다음 청크에 설정된 이전 청크의 사이즈와 일치하는지 확인한다. prev_size

그렇지 않으면 오류가 발생한다.

제거를 용이하게 하기위해 인접한 청크들의 포인터를 잘 조정한다.

P -> fd  -> bk = P -> bk

P -> bk -> fd = p -> fd

void malloc_consolidate(mstate av)

free()의 특수화 된 버전

1. global_max_fast가 0 (초기화되지 않음)인지 확인한다. 값이 0이면 매개 변수로 av를 사용하여 malloc_init_state를 호출하고 리턴

Fast bin이 처리하는 메모리의 최대 크기는 global_max_fast에 의해 결정된다.

2. global_max_fast가 0이 아니면 av에 대해 FASTCHUNKS_BIT를 지웁니다.

3. 첫 번째 인덱스에서 마지막 인덱스까지 fastbin 배열을 반복합니다. 

1) 현재 fastbin 청크에 잠금을 설정하고 null이 아닌 경우 계속 진행한다.

2) 이전 청크가 사용 중이 아니면 이전 청크에서 unlink를 호출한다.

3) 다음 청크가 TOP chunk가 아닌 경우 :

1>다음 청크가 사용 중이 아니면 다음 청크에서 unlink를 호출한다.

2>청크를 이전과 병합한 다음 통합 된 청크를 unsorted bin의 헤드에 추가한다.

4. next chunk가 TOP chunk인 경우, 청크를 하나의 TOP 청크로 적절하게 병합한다.

NOTE : 'in use'에 대한 점검은 PREV_IN_USE 플래그를 사용하여 수행된다. 따라서 다른 fastbin 청크의 free는 확인되지 않는다.

Bin

bin은 더블이나 싱글로 link된 free(할당되지 않은) chunks의 리스트이다.  청크의 크기에 따라 bin의 종류가 달라지는데

1. Fast bin     2. Unsorted bin    3. Small bin    4. Large bin 이 있다.

 Fast bin은 아래와 같이 관리된다.

Unsorted, small 과 large bin은 단일 배열을 사용하여 관리된다.

초기에, 프로세스 초기화 과정에 small, large bin은 비어있다.

각각의 bin은 배열의 두개의 값으로 표현되는데, bin리스트의 'HEAD'와 'TAIL' 포인터이다. fast bin은 싱글 링크드 리스트 구조이고, 두번째 값(TAIL)은 NULL값을 가진다.

Fast bins

패스트빈은 10가지 종류가 있다. 모두 다 싱글 링크드 리스트 구조이며 추가 삭제는 리스트의 앞쪽에서 일어난다. Last In First Out 구조를 가진다.

하나의 패스트빈은 모두 같은 사이즈의 chunks의 집합으로 이루어져있고 사이즈는 16 / 24 / 32 / 40 / 48 / 56 / 64 / 72 / 80 / 88 이 있다.

인접한 두개의 free된 fast chunk는 병합되지 않는다. 할당할 때에는 먼저 할당하려는 사이즈와 같은 크기의 사용하지 않는 청크가 fastbin에 존재

하는 지를 검사한다. 만약 존재한다면 바로 fastbin에서 빼오고 반환한다. 만약 없다면 다른 방식(top chunk 절단)을 통해 크기가 적합한 청크를 

얻어와 반환한다. 하나의 청크를 프리(free)할 때에도, 먼저 해당 청크의 크기가 fastbin의 범위 안에 있는 지를 검사한다. 만약 있다면 그에 대응하

는 bin에 넣는다. 이름을 보면 뜻을 알 수 있다고, fastbin은 비교적 작은 사이즈의 청크들을 분배하고 회수한다. 그렇기 때문에 위에서 얘기한 bk

에 대한 작업은 진행하지 않는다. 그저 fd만 사용하여 더블 링크드 리스트가 아닌 싱글링크드 리스트를 구성하며 LIFO 원칙을 준수한다.

Unsorted bin

모든 chunk들은 free되어 처음에 unsorted bin에 추가된다. 최근에 free된 chunk들을 재사용 할 수 있도록 하기 위함.

First In First Out 형태로 동작하며 검색된 chunk는 바로 재할당 되더라도 원래의 bin으로 돌아가게 됨. 단 한번의 재사용 기회가 주어짐

double linked 리스트 구조를 갖으며 개수는 1개이다. 속도 향상

Small bin

small bin은 62 종류를 가지며 fast bin 보다는 느리지만 Large bin 보다는 빠르다. 더블 링크드 리스트 구조이며 First In First Out 방식으로 

'HEAD'에서 삽입이 발생하는 동안 'TAIL'에서 삭제가 발생한다. fast bins처럼 같은 사이즈의 청크끼리 묶이며 사이즈는 16, 24 ... , 504바이트(8바이트 단위) 등

32bit

size : 0x10, 0x18, 0x20 ...... , 0x1F8(504)

• (8x+8, 1<=x<=62) 
• 
  
• 
  
• 64bit

---

• size : 0x20, 0x30, 0x30 ...... , 0x3F0(1008)
  (16x+16, 1<=x<=62)

이 있다. free된 두개의 청크가 있다면 병합을 진행한다.

Large bin

63가지의 bin을 가지며 더블 링크드 리스트 구조를 가진다. 512바이트 이상의 크기를 가지는 chunk모으며 크기가 같은 청크만 모으지 않는다.

'HEAD'에서 가장 큰 청크, 'TAIL'에서 가장 작은 청크 등의 순서로 정렬된다. 

fd_nextsize와 bk_nextsize에 대한 필드가 존재한다고 생각하면 되고, 역시 인접한 두 청크가 free상태이면 병합을 진행한다.

만약 128KB 이상의 공간이 할당되는 경우에는 mmap() 시스템 콜을 거쳐 별도의 공간을 할당한 뒤에 청크가 생성된다.

그리고 이렇게 생성된 청크들은 bin에 속하지 않는다. IS_MMAPPED플래그로 체크하며 munmap()으로 해제한다.

malloc_state

Arena

아레나는 malloc()에서 메모리 관리 부분을 포함한 Main, thread에 대한 힙 영역이다.

이 구조체는 Arena의 헤더 세부 정보를 나타낸다. 메인 스레드의 영역은 전역 변수이며 힙 세그먼트의 부분이 아니다. 메인 스레드 이외에 아레나의 헤더(malloc_state 구조체)는 각각의 힙 세그먼트에 저장됩니다.