[glibc] malloc - 1

Heap

요청에 따라 할당되는, chunk의 형태로 나뉠 수 있는 (인접한)연속된 메모리 영역을 의미한다. 

예전에는 한 어플리케이션에 하나의 힙만 존재했지만, 지금은 한 어플리케이션이 여러 힙을 가질 수 있다.

각각의 heap은 하나의 arena에만 속할 수 있다.

Chunk

실제로 ``c malloc()``으로 할당/반환받게 되는 영역을 말한다. 8 bytes의 배수로 할당된다.

* 64bit OS에서는 16 bytes의 배수로 할당된다.

Glibc's malloc은 chunk-oriented다. 커다란 heap을 다양한 사이즈의 chunk로 나눠 할당한다.

하나의 chunk는 하나의 heap 내부에 존재하며, 당연히 하나의 arena에 속한다.

각 chunk는 size가 얼마인지, adjacent chunk의 위치는 어디인지를 나타내는 meta-data를 포함한다.

• chunk가 free되면 그 공간을 재사용할 수 있도록 linked list 형태의 arena-related information에 추가한다.
• free'd chunk의 마지막 `` word``(type)는 chunk size의 복사본을 가지고 있으며, 이 `` word``의 3 LSBs는 0으로 설정된다.
• chunk의 앞쪽에 있는 원래 chunk size의 3 LSBs는 flags로 사용된다.
  * chunk는 8 bytes의 배수이기 때문에 3 LSBs를 flag로 사용할 수 있다.
• chunk의 최소 크기는 ``c 4*sizeof(void*)``이다.
  생각해보면 `` size, fwd, bck, prev_size``를 모두 담으려면 저 사이즈가 필요하다.

In-use Chunk	Free Chunk

• `` mchunkptr``이 `` prev_size``를 가리키고 있고 `` chunk`` 구조체가 여기서 부터 시작하기 때문에, 위 그림과 달리 상단의 `` prev_size``부터 chunk가 시작한다고 보는게 편하다. 위는 하단의 `` prev_size``까지 `` payload``로 사용하기 때문에 이렇게 표현한 듯.
• malloc이 반환하는 주소가 chunk의 시작 지점이 아니라 `` payload``다. 따라서 반환되는 위치부터 바로 포인터로 접근해 쓸 수 있다.
  
• `` prev_size`` field가 존재하는건 이를 보고 이전 chunk와 merge하기 위해.

flags

A : `` NON_MAIN_ARENA (0x04)``

`` 0``이면 이 chunk는 main arena와 main heap에서 왔다는 것을 의미한다.

`` 1``이면 이 chunk는 mmap'd memory에서 왔다는 것을 의미한다. 이 경우 chunk's address를 이용해 heap_info의 위치를 계산할 수 있다.

M : `` IS_MMAPPED (0x02)``

chunk 자체가 단일 ``c mmap()`` 호출로 할당된 영역 전체일 때 set된다. 따라서 어떤 heap의 일부가 아니라, ``c mmap()``으로 할당된 영역 그 자체가 모두 chunk임을 의미한다.

P : `` PREV_INUSE (0x01)``

실제로는 Previous chunk should not be considered a candidate for coalescing. 를 의미한다.

그래서 chunk가 사용되고 있는 경우 / fastbins에 들어가는 chunk일 경우 set된다.

Arena

arena는 하나 또는 여러 heap들의 reference나, heap chunk들의 linked lists("bins")를 포함하고 있는 구조(structure)를 말한다.

arena는 원래 한 번 크게 할당한 다음 이를 직접 나누어 부분 부분 접근하는 용도로 사용하는 크고 연속적인 메모리 영역을 의미한다.

```c

char *arena = (HUGE_SIZE);

...

char *p = arena + offset;

```

• main_arena는 application's initial heap만 사용한다.
  
• 다른 arena는 mmap'd heap을 사용한다.
  
• main_arena를 제외한 arenas는 additional arenas를 가리키는 `` next`` pointer를 가지고 있다.
  
• arenas는 "top" chunk를 가리키는 포인터를 가지고 있다.
  * top chunk는 아직 할당하지 않은, 힙의 최상단에 있는 chunk를 의미한다.

Heaps and Arenas ( Except main_arena )

* main_arena는 heap_info가 없으며 arena 구조 자체도 heap에 존재하는게 아니라 libc.so의 data segment에 존재한다.

bins

arena에는 free'd chunks를 빠르게 재할당할 수 있도록 free'd chunk를 종류 별로 가리키는 포인터의 리스트를 가지고 있는데, 이를 "bins"라고 한다.

Note ) chunk는 항상 ``c (fast)bins[]`` 바로 다음(리스트의 왼쪽)에 추가된다.

``c fastbins[]``는 LIFO 이므로 맨 왼쪽 chunk가 먼저 serve되며,

``c bins[]``는 FIFO 이므로 맨 오른쪽 chunk가 먼저 serve된다. 따라서 ``c bins[].bk`` 번지의 chunk가 다음 반환 chunk다.

Free, Unsorted, Small, and Large Bin Chains

fastbin

같은 크기를 기준으로 linked list로 연결된 일정 크기 이하의 작은 chunks를 의미한다.

single-linked list 구조로 연결되었기 때문에, stack과 같은 LIFO 구조다.

인접 chunk와 consolidate 되지 않는다!!!!(`` P`` flag) 그리고, 시스템에 리턴되지 않는다.

사용하면 fragmentation이 증가하지만, 같은 크기에 대한 할당 요청을 빠르게 처리할 수 있게 된다.

``c mallopt(M_MXFAST, value);``를 지정해 fastbins를 사용할 size limit를 설정할 수 있다.

default value는 ``c 64*sizeof(size_t)/4``이기 때문에 32bit os의 경우 ``c mchunkptr.size == 0x40``까지 fastbin으로 분류된다.

``c 0-80*sizeof(size_t)/4``까지 지정 가능하다. ``c 0``이면 fast bins 비활성화.

Unsorted bin

top chunk가 아닐 경우, chunk가 free되면 바로 계산되어 small bin / large bin으로 들어가는게 아니라, 일단 Unsorted bin으로 들어가서 재할당을 기다리게 된다.

따라서 unsorted bin이 small bin / large bin에 chunk를 추가하는 유일한 지점이다.

unsorted bin == 단일 chunk라고 생각해서는 안된다. unsorted bin도 linked-list이기 때문에, 여러 chunk가 연결될 수 있다.

small bin chunk가 unsorted bin에 존재하는 상태에서 또 다른 small bin chunk가 free되는 경우

이를 계속 unsorted bin에 추가하다가, fastbin같은 다른 size의 chunk가 free될 때 small bin으로 옮긴다.

* small bin으로 분류되지만 다른 size를 가진 chunk인 경우에도 unsorted bin에 추가한다.

Small bin

``c MINSIZE < sizeof(chunk) < 512``인 경우. 따라서 fastbin size를 포함한다.

각 bin마다 chunk가 동일한 크기를 가진다.

fastbin과의 차이점은 `` P`` flag가 없어 일단 chunk가 small bin에 연결되면 인접 chunk와 합치려고 한다는 점,

그리고 circular doubly linked list 구조라는 점이다.

인접 chunk와 모두 결합하기 때문에 small bin's chunk는 인접 chunk가 없다.

* fast, unsorted, in-use chunk와 인접해있는 경우는 결합하지 않기 때문에 인접 chunk가 있을 수 있다.

chunk 반환 순서

``c smallbin.fd``도 ``fastbin.fd``와 동일하게 제일 최근에 반환된 chunk를 가리키고 있다.

그러나 fastbin이 제일 최근에 반환된 chunk를 반환하는 LIFO 구조인 반면,

smallbin은 FIFO 구조다. 따라서 리스트에 제일 오래 있었던 chunk를 반환하며 이는 리스트의 맨 마지막에 있는 chunk이므로 ``c smallbin.bk``가 가리키는 chunk다.

Large bin

각 bin마다 chunk가 일정 범위의 크기를 가진다. chunk가 크다면 여기로 들어온다.

circular doubly linked list구조이며, 요청에 가장 알맞는 크기의 chunk를 찾는 작업이 필요하기 때문에 

이를 위해 `` fd_nextsize/bk_nextsize``라는 추가적인 circular doubly linked list를 사용한다.

요청을 처리하기 위해 chunk가 나뉠 수도 있다.

Large Bin "Next Size" Chains

* 요청 사이즈를 만족하는 chunk가 여러 개 있을 경우, 보통 두 번째가 선택되는데 이는 첫 번째 chunk를 선택하면 `` **_nextsize`` 포인터를 다시 이어야 해서 번거롭기 때문이다.

multi-thread and arenas

기본적으로는 thread 마다 각각의 heap arena를 가지고 있으며 main thread가 사용하는 arena는 main_arena다.

그러나 무조건 thread의 수 만큼 arena가 존재하는 것은 아니며 현재 시스템의 core 수, os bit에 따라 가질 수 있는 최대 arena 수가 결정되기 때문에 thread가 많아질 경우 여러 thread가 arena를 공유할 수도 있다.

그래서 access control을 위해 각각의 arena는 mutex를 가지고 있다.

* 단, fastbin에 접근하는 것과 같은 atomic operations는 arena lock을 필요로 하지 않는다.

---

참고

https://sourceware.org/glibc/wiki/MallocInternals

https://sploitfun.wordpress.com/2015/02/10/understanding-glibc-malloc