Memory Allocator Tutorial
Memory allocator는 어떤 byte들이 할당되었는지, 사용할 수 있는지 알고있어야합니다. 이 포스트에서는 malloc과 free를 수행하는 실제 코드를 통해 allocator의 동작과 allocator를 구성하는 개념을 알아보겠습니다.
This page talks about links of blocks - do I malloc memory for them instead?
비록 개념적으론 Linked List와 block의 list 만든다고 생각할 수 있지만, 이것을 만들기 위해 malloc memory가 필요하지는 않습니다. 대신 우리가 사용할 수 있는 메모리에 integer와 pointer를 정보를 작성한다면 한 주소에서 다음 주소로 계속해서 찾아갈 수가 있습니다. 이러한 내부 정보를 저장하는 데에는 약간의 overhead가 필요합니다. 그래서 만약 시스템으로부터 1024KB의 연속된 메모리를 제공받았더라도 그들 전부를 동작하는 프로그램에 사용할 수는 없습니다(overhead가 사용할 공간이 필요).
Thinking in blocks
우리는 heap memory가 각각의 block이 할당되거나 할당되지 않은 block의 list라고 생각할 수 있습니다. 포인터들의 목록을 명시적으로 저장하기보다는 블록의 일부분에 블록의 사이즈에 대한 정보를 저장합니다. 그러므로 사용할수 있는 블록들이 존재한다고 해도, 그들을 바로 알 수는 없습니다(암시적이다). 예를 들어 각각의 블록의 일부분에 블록의 사이즈 정보 형식을 저장할 경우 그들을 통해서 알수 있습니다.
블록의 사이즈를 더함으로써 한 블록에서 다음 블록으로 이동할 수 있습니다. 예를 들어 p라는 포인터가 블록의 시작지점을 가리킬 때,만약 블록의 크기 단위가 바이트라면, 다음 블록인 next는 ((char*) p _ *(size_t *)p)입니다. car*로 강제형변환을 해줌으로서 포인터 연산이 바이트단위로 이루어짐을 알 수 있습니다. size_t로 의 강제형변환은 p의 메모리를 size value라는 것을 보증합니다. 이것은 p가 만약 void*나 char*라면 반드시 필요합니다.
이러한 값들은 memory allocator 내부에서 수행되기 때문에이것을 호출하는 프로그램은 이러한 값들을 알 수 없습니다.
예를 들어. allocator가 80바이트를 예약해달라고 요청받았다면 8 바이트의 internal head data가 필요하다고 가정해봅시다. 이 경우 allocator는 적어도 88바이트의 할당되지 않은 공간이 필요할 것입니다. heap data를 업데이트 한 이후에 allocator는 block의 pointer를 리턴해줄 것입니다. 하지만 이 return된 포인터는 block의 start지점을 가리키지 않습니다. block의 start 지점은 internal size data가 저장되어 있기 때문이다. 리턴되는 값은 블록의 시작지점으로부터 8 바이트 떨어진 지점입니다. 실제 구현에서 포인터 연산은 자료형에 의존한다는 것을 기억해야 합니다. 예를 들어 p+=8은 8바이트를 더하는 것이 아닌 8*(sizeof(p))를 더하는 것입니다.
Implementing malloc
가장 단순한 malloc 동작 방법은 first fit을 사용하는 것입니다. 처음 블록부터 시작해서 할당되지 않은 충분한 사이즈가 발견되거나 모든 블록을 체크할 때까지 반복합니다.
만약 적절한 block이 없다면 sbrk를 호출해 heap의 size를 적절히 늘립니다. 이 때 sbrk를 통해 충분한 양을 요청해 근시일 내에 또 sbrk로 요청할 일이 없도록 하는 것이 빠른 구현 방법입니다. (sbrk가 system call이므로 library call 보다 overhead가 큼)
적절한 블록의 발견했다면 이 블록은 우리가 필요로 하는 블록보다 클 수 도 있습니다. 이러한 경우 2개의 블록으로 나눠 첫번째 블록에 넣어 할당된 블록을 만들고 두 번째 블록을 남겨놓습니다.
블록이 사용가능한지 불가능하지 표시하는 방법엔 단순한 2가지 방법이 있습니다.
첫번째는 header information의 size와 함께 바이트로 저장하는 방법이 있고, 두 번째로는 size 정보의 가장 마지막 bit에 표시하는 방법이 있습니다. size의 마지막 비트에 저장할 경우에는 블록 size는 짝수만 가능합니다. (마지막 비트가 사용 가능한지 불가능한지 표시해야 하기 때문에) 이 블록이 사용가능한지 불가능한지의 판별은 다음과 같은 비트 연산을 통해 가능합니다.
// Assumes p is a reasonable pointer type, e.g. 'size_t *'. This gets very sinister when you implement coalescing and splitting (next section).
isallocated = (*p) & 1;
realsize = (*p) & ~1; // mask out the lowest bit
Alignment and rounding up considerations
많은 architecture들은 여러 바이트로 이루어진 primitive들이 2^n의 배수로 정렬될 것은 기대합니다. 예를 들어 4바이트를 요구하는 타입이 4바이트 바운더리에서 정렬되길 바랍니다. 만약 multi-byte orimitives가 합리적인 경계 안에 저장되지 않는다면 (예를 들어 홀수로 시작하는 주소값) 효율에 상당한 영향을 끼칠것입니다. 왜냐하면 이렇게 저장된 자료는 두번의 memory read가 필요하기 때문입니다. 몇몇의 architecture에서는 더 큰 penalty를 받습니다.(프로그램이 bus error로 충돌) - (구조체의 padding이 들어가는 것과 유사)
malloc은 사용자가 할당된 메모리에 어떤 자료형을 사용할 지 알수 없기 때문에, 프로그램에 반환되는 포인터는 최악의 경우를 대비해 align된 포인터를 반환할 필요가 있습니다.
glibc 문서에 따르면 glibc의 malloc은 다음과 같은 heuristic을 사용합니다. : malloc이 반환하는 블록은 어떠한 자료형이든 담을 수 있게 정렬되는 것을 보장해야 합니다. GNU system에서 주소값은 항상 8의 배수여야 하고, 64bit 시스템에서는 16의 배수여야 합니다.
예를 들어 만약 얼마나 많은 16byte unit이 필요한지 계산할 필요가 있다면 다음과 같이 반올림하는 것을 잊지 말아야 합니다.
int s = (requested_bytes + tag_overhead_bytes + 15) / 16
뒤에 15를 더해 16바이트를 꽉 채우지 못한 unit을 올림 해주는 것을 보장합니다. 실제 코드는 15와 같이 쓰는 것보다 sizeof(x)-1과 같이 symbol size를 이용합니다.
A note about internal fragmentation
Internal fragmentation은 할당된 사이즈보다 더 큰 블록을 제공할 때 발생합니다. metadata를 포함하지 않은 16바이트의 할당되지 않은 블록이 있다고 했을 때, 7바이트를 할당하길 원한다면 16바이트블록 전부를 반환하길 원할수도 있습니다.
이것은 다음 section에 나올 병합과 분할을 구현할 때 매우 불길한 상태가 됩니다. 만약 구현하지 않는다면 7 바이트할당을 위해서 64바이트의 블록을 반환하는 경우가 생길수도 있습니다. 이러한 allocation의 큰 overhead를 피하도록 해야 합니다.
Implementing free
free가 호출될 때 실제 시작 지점으로 돌아가기 위해 offset을 다시 적용해야 합니다(사용자가 받은 포인터는 실제 블록의 시작 지점이 아니므로 - header에 사이즈 정보등을 저장).
단순한 구현은 블록의 사용 정보를 사용하지 않음으로 표시하는 것입니다. 만약 사이즈의 가장 마지막 비트에 사용 정보를 저장했다면 그 비트를 clear해주는 것입니다.
*p = (*p) & ~1; // Clear lowest bit
하지만 이것을 포함해 몇가지 작업이 더 필요합니다. 만약 현재 블록과 다음 블록(존재한다면)이 둘다 사용 가능한 상태라면 두 블록을 하나의 블록으로 합쳐주는 것이 필요합니다. 이와 마찬가지로 현재 블록과 전 블록이 사용가능하다면 같은 작업을 해줘야 합니다. 할당되지 않은 메모리가 존재한다면 이들을 합병해 하나의 블록으로 만들어줘야 합니다.
이러한 작업을 하기 위해서는 현재 블록의 이전 블록을 찾을 수 있어야 합니다. 이전 블록을 찾기 위해서 블록의 끝에도 블록 사이즈를 저장해야 합니다. 이것들은 boundery tags라고 불립니다.
블록들은 연속되어 있으므로, 블록의 끝은 다음 블록의 시작점 바로 옆에 있습니다. 그러므로 현재 블록(첫번째 블록으로부터 떨어진)은 앞의 몇바이트를 살펴봄으로써 이전 블록의 사이즈를 알 수 있습니다. 이러한 정보를 통해 전 블록의 시작지점으로 뛸 수 있습니다.
Performance
지금까지의 설명으로 memory allocator를 작성하는 것이 가능합니다. 가장 중요한 장점은 단순함입니다. 메모리를 할당하는 것은 최악의 경우 선형 시간으로 동작합니다. (충분히 큰 할당 가능한 블록들의 linked list를 검색하는데 걸리는 시간) 할당 해제에는 constant time이 소모됩니다. (하나의 블록으로 합치는데 3개 이상의 블록을 볼 필요가 없습니다.) 이 allocator를 이용하면 다른 배치 전략을 실험해 볼 수 있습니다. 예를 들어 마지막으로 free시킨 블록부터 검색한다던가, 마지막으로 할당했던 블록부터 검색하는 방식 등으로 사용해서 말입니다. 만약 블록에 포인터를 저장해둔다면 이 포인터들이 항상 유효한 상태로 남아있도록 신경써야 합니다. (예를 들어 블록들을 합병하거나 힙의 구조를 바꾸는 다른 malloc이나 free 호출등을 통해 unvaild한 상태가 되는 것을 방지)
Explicit Free List Allocators
free node들에 대해 명시적으로 doubly-linked list를 수행함으로서 성능을 향상시킬 수 있다. 이러한 경우, 이전 free 블록과 다음 free 블록을 즉시 이동할 수 있다. 이러한 linked list는 오직 할당되지 않은 블록들만을 포함하고 있기 때문에 검색 시간을 줄일 수 있다.
두 번째 장점은 Linked List의 순서를 어느정도 제어할 수 있다는 점입니다. 예를 들어 블록이 free되면 이웃들 사이에 놓이는 대신 linked list의 시작부분에 삽입되는 방식 등으로 말입니다. 이에 대해서는 아래에서 다시 한번 살펴보겠습니다.
이러한 linked list의 포인터는 어디에 저장해야 할까요? 가장 간단한 트릭은 블록 자체는 사용되지 않도록 하고 그 이전 블록과 다음 블록의 포인터를 블록의 일부로 저장하는 것입니다. 이러한 경우 이 free block은 2개의 포인터를 저장하기에 충분한 크기를 보장해야 합니다.
블록을 정확하게 free 시키고 그들의 두 이웃과 합병시켜주기 위해서는 여전히 boundery tag가 필요합니다. 즉 , explicit free lists는 더 많은 코드와 복잡도를 필요로 합니다.
이러한 explicit free lists를 사용하면 빠르고 간단한 find-First 알고리즘을 구현할 수 있습니다. 하지만 list link order가 수정될 수 있으므로 이 순서에 따라 다른 배치 전략을 구현할 수 있습니다. 예를 들어 linkede list가 가장 큰 것부터 작은 순서대로 연결되어 있다면 Worst-fit 배치 전략을 수행하게 됩니다.
-Explicit linked list insertion policy
새롭게 free된 블록은 두 가지 가능한 위치에 쉽게 삽입될 수 있습니다. 첫째로는 리스트의 맨 처음, 또는 주소 순서대로 입니다. 주소 순서대로는 boundery tag를 이용해 찾는 첫번째 이웃을 이용하는 것입니다)
list의 맨 처음에 삽입하는 것은 LIFO policy를 따릅니다. 가장 최근에 free된 공간을 재사용 하는 것입니다. 이와 관련된 연구는 address order를 이용하는 것보다 fragmentation이 심해질수 있다고 합니다.
address order에 따라 free된 블록을 삽입하는 것은(Address ordered policy) 주소가 증가하는 순서대로 방문하게 됩니다. 이 policy는 boundey tag를 이용해서 다음과 이전에 할당되지 않은 블록을 찾아야 하므로 list의 가장 처음에 삽입하는 것보다 시간이 더 오래 걸립니다. 하지만 fragmentation이 더 적게 일어납니다.
Case Study : Buddy Allocator(an example of a segregated list)
분리된 allocator는 힙을 두개의 영역으로 나눕니다. 두 영역은 각각 다른 allocator에 의해 관리되며, 이 allocator들은 allocation request size에 따라 선택됩니다. size들은 2개의 클래스로 나뉘며 각각의 사이즈는 다른 sub-allocator에 의해 관리되고 각각의 size는 각자 free list에 의해 유지됩니다.
이러한 타입의 잘 알려진 allocator는 buddy allocator입니다. 여러가지 할당자들이 존재하지만 우리는 2^n의 배수로 블록을 나누는 binary buddy allocator에 대해 알아보겠습니다. 기본 컨셉은 단순합니다. 만약 2^n 사이즈의 free block이 존재하지 않는다면 다음 레벨로 가서 블록을 뺏어 두개로 쪼개는 것입니다. 만약 같은 사이즈의 두 이웃 블록이 할당되지 않았다면, 이 두 블록을 두배의 크기를 가진 하나의 큰 블록으로 합칩니다.
buddy allocator는 합칠 이웃 블록이 현재 free된 블록의 주소에서 계산되므로 size tags를 검색하는 것보다 더 빠릅니다. 최종 성능은 가장 작은 0이 아닌 비트를 찾는 특별한 CPU instruction을 사용하므로 적은 양의 assembler code만을 필요로합니다.
buddy allocator의 가장 큰 단점은 internal fragmentation이 커지는 것입니다. 왜냐하면 allocation은 가장 큰접한 크기로 올림하기 때문입니다. 예를 들어 buddy allocation에서 68 byte를 allocation하기 위해서는 128 byte 블록이 필요합니다.
