Chapter 9. Virtual Memory - Dynamic Memory Allocation
Computer Systems : A Programmer’s Perspective (CSAPP)
9.9 Dynamic Memory Allocation
9.8절에서 살펴본 mmap과 munmap 함수로도 low-level에서 가상 메모리의 영역을 생성하고 삭제할 수 있다. 하지만 run-time에서 필요한 가상 메모리를 얻고자 할 때는 dynamic memory allocator 를 사용하는 것이 훨씬 편리하다.
Dynamic memory allocator는 heap이라고 부르는 프로세스의 가상 메모리 영역을 관리한다. 시스템마다 구체적인 것은 다르겠지만, heap은 uninitialized data(.bss 영역) 위부터 시작해서 위쪽으로 올라가는 영역이다. 커널은 각 프로세스마다 heap의 가장 위쪽을 가리키는 포인터 brk을 관리한다.
Allocator는 heap을 여러 block 들의 집합체로 관리하는데, 각 block은 allocated / free 둘 중 하나의 상태에 있는 가상 메모리의 연속된 뭉치(contiguous chunk)이다. Allocated 블록은 현재 응용 프로그램이 사용 중이라고 명시적으로 맡아 놓은 상태이고, free block은 새로 할당될 수 있는 상태이다. Free block은 따로 할당할 때까지 계속 free 상태이고, allocated block은은 응용 프로그램에서 직접, 혹은 memory allocator이 내부적으로 free하기 전까지 allocated 상태로 남는다.
Allocator에는 두 가지 스타일이 있다. 두 스타일 모두 새 블록을 할당하는 건 응용 프로그램(application)에게 맡기지만 free하는 것을 누구에게 맡길지에는 차이가 있다.
- Explicit allocators : 응용 프로그램에서 명시적으로 할당됐던 블록을 free 하도록 한다. 이를 위한 함수들은 C 표준 라이브러리에서
malloc패키지의 함수들에 제공된다. - Implicit allocators : 위와 반대로 allocator가 직접 더이상 사용되지 않는 할당된 블록을 찾아서 free 하도록 한다. Garbage collector라고도 불리고 ML, Lisp, Java 등의 고급 언어에서 사용된다.
9.9.1 The malloc and free Functions
C 표준 라이브러리는 malloc 패키지라고도 알려진 expliit allocator를 제공한다.
#include <stdlib.h>
void *malloc(size_t size);
malloc 함수를 불러서 heap의 블록을 할당할 수 있다. 반환값은 할당한 블록의 포인터인데, 이때 요청된 size 바이트만큼 딱 할당되지 않고 특정 단위로 aligned되어 할당된다. 예를 들어 32비트 모드에서는 8바이트 단위로 aligned된 블록을 할당하고 64비트에서는 16바이트 단위로 align해서 할당한다.
사용 가능한 가상 메모리를 초과하는 등의 문제가 생겼을 경우 NULL을 반환하고 errno의 값을 설정한다. 또한 malloc은 할당한 블록의 초기값을 따로 설정하지 않는다. 초기화를 하고 싶은 경우 wrapper function인 calloc을 사용하면 되고, 이전에 할당한 블록의 크기를 바꾸고 싶은 경우 realloc을 사용한다.
mmap과 munmap으로 직접 heap을 할당하거나 할당 해제할 수도 있지만 sbrk 함수를 이용할 수도 있다.
#include <unistd.h>
void *sbrk(intptr_t incr);
sbrk 함수는 커널이 관리하는 brk 포인터에 incr만큼 더해서 heap을 올리거나(grow) 내릴 수 있다(shrink). 반환값은 변하기 전 brk의 값이고, 에러인 경우는 -1을 반환하고 errno의 값을 ENOMEM으로 설정한다. incr이 0이면 현재 brk를 반환하고,incr이 음수인 경우도 동작한다.
프로그램은 free 함수를 이용해서 heap에 할당된 블록을 할당 해제할 수 있다.
#include <stdlih.b>
void free(void *ptr);
free 함수는 반드시 malloc, calloc, realloc으로 할당했던 블록의 시작 부분 포인터를 argument로 넣어 줘야 한다. 그렇지 않으면 undefined behavior가 발생하는데 free는 원래 반환값이 없기 때문에 무언가 잘못되었다고 알려주지 않는다. 9.11절에서 이런 경우 발생하는 run-time error를 살펴볼 것이다.
예시를 통해서 malloc과 free의 동작을 간단히 살펴보자.
한 칸은 1 word(=4 byte)를 의미하고, 이 예시에서는 8-byte align된다고 가정한다.
주목할 부분은 (b)이다. 5 word를 malloc했지만 우리는 2 word 단위로 align하기 때문에 마지막 한 word는 남겨둔다. 그리고 (c)에서 6 word를 할당하면 pad된 곳 이후부터 할당한다.
(d)에서 p2가 가리키는 블록을 free하면, p2가 가리키던 5 word는 새로 할당될 수 있는 상태가 되어서 (e)에서 p4가 이곳을 할당받게 된다. 하지만 포인터 p2는 아직 저곳을 가리키고 있기 때문에 사용자는 p2를 다시 사용하지 않도록 주의해야 한다.
9.9.2 Why Dynamic Memory Allocation?
‘동적’ 메모리 할당의 가장 중요한 점은, 사용자가 프로그램을 돌리기 전까지 얼마나 할당될 지 보통 알지 못한다는 것이다.
만약 우리가 stdin으로 문자열을 입력받아 저장하는 프로그램을 짠다고 하면, 가장 단순한 방법은 MAX값을 큰 수로 설정해서 크기가 하드코딩된 배열을 사용하는 것이다.
하지만 이는 좋은 방법이 아니다. 임의로 설정한 MAX라는 값은 실제 프로그램과 아무 관련도 없기도 하고, 배열의 크기를 하드코딩해 놓으면 그 이상의 입력이 들어왔을 때의 유일한 대처 방법은 MAX를 더 크게 잡고 다시 컴파일하는 것 뿐이다. 수백만 줄의 코드와 수많은 사용자가 있는 응용 프로그램에서 이렇게 하드코딩된 배열 크기는 유지보수에 있어 악몽과도 같은 상황을 만들게 된다.
더 나은 방법은 run time에 배열의 크기 n이 정해지고 나서 배열을 위한 메모리를 동적으로 할당하는 것이다. 이 방법을 사용하면 배열 크기를 제한하는 것은 가상 메모리의 전체 용량뿐이다.
동적 메모리 할당은 아주 유용하고 중요한 기술이지만 잘 알고 사용하지 않으면 여러 에러가 발생할 수 있다. 이는 9.11절에서 다룬다.
9.9.3 Allocator Requirements and Goals
Explicit allocator는 다음과 같은 꽤 엄격한 제약 조건 하에서 작동해야 한다.
- 임의로 들어오는 request들에 대응할 수 있어야 한다.
프로그램은 allocate/free 요청을 임의의 순서(단, free는 할당했던 블록에 대해서만)로 할 수 있기 때문에 allocator는 alloc 후 free가 꼭 나온다던가, alloc과 free가 짝을 이루어 nested된다던가 하는 가정을 할 수 없다. - Request에 즉시 대응해야 한다.
alloc/free 요청들의 순서를 바꾼다던가 buffer을 사용한다던가 할 수 없다. 할당 요청이 오면 즉시 대응한다. - Heap만 사용해야 한다.
- Aligned되도록 할당해야 한다.
- 할당된 블록은 수정할 수 없다.
Allocator는 free 블록만 건드릴 수 있고, 일단 할당된 블록은 수정하거나 위치를 옮길 수 없다. 따라서 성능을 올리기 위해 할당된 블록들을 compaction한다던가 할 수 없다.
이런 제약 조건 하에서 allocator는 두 가지 관점에서의 성능을 높여야 한다.
- 목표 1: Throughput을 최대로
Throughput이란 단위 시간당 처리할 수 있는 요청의 개수이다. 예를 들어 1초에 500번 alloc, 500번 free할 수 있다면 throughput은 1000/s가 된다.
alloc/free 요청에 걸리는 시간을 줄여서 throughput을 최대화할 수 있다. 최악의 경우에 alloc에 걸리는 시간을 free block 개수에 선형으로, free에 걸리는 시간은 상수로 하는 allocator를 만드는 것은 크게 어렵지는 않다. - 목표 2: Memory utilization을 최대로
초보 프로그래머는 가상 메모리가 무제한이라고 착각하곤 한다. 하지만 시스템 내에서 모든 프로세스가 할당받을 수 있는 가상 메모리는 디스크의 swap space 만큼으로 제한되어 있다.
가상 메모리도 효율적으로 사용해야 하는 유한한 자원이고, 크기가 큰 블록을 alloc/free할 때 특히 그렇다.
Allocator가 heap을 얼마나 효율적으로 사용하는지는 여러 방법으로 살펴볼 수 있다.
가장 유용한 측도는 peak utilization 이다. 단조증가하는 Heap의 크기를 $H_k$ 라고 하고 n개의 alloc/free 요청들 $R_0, R_1, …, R_{n-1}$ 이 들어온다고 하자. k번째 요청에 대한 동작이 끝난 시점에서 할당된 블록들의 payload의 총 합을 $P_k$ 라고 했을 때, peak utilization $U_k$는 다음과 같다.
\(U_k = \frac{max_{1<=k} P_{i}}{H_k}\)
Allocator의 목적은 전체 sequence에서 peak utilization $U_{n-1}$를 최대로 만드는 것이다. 곧 보겠지만, throughput과 peak utilization 간에는 trade-off가 존재해서 heap utilization을 포기하면 throughput을 최대로 하는 allocator를 쉽게 만들 수 있다. 여기서 중요한 도전 과제는 둘 사이의 적절한 균형을 찾는 것이 된다.
9.9.4 Fragmentation
Heap utilization이 낮아지는 주요한 원인은 fragmentation 이라고 불리는 현상으로, 사용 중이 아닌 메모리가 할당 요청을 만족시킬 수 없는 경우 발생한다.
Internal fragmentation 은 할당된 블록이 실제 사용되는 용량(payload)보다 큰 경우 발생한다. 발생하는 원인은 여러 가지인데, 예를 들어 allocator가 메모리 블록을 할당할 때 요청받은 payload보다 큰 블록 중에 최소의 크기인 것에 할당하는 식으로 구현되었을 수도 있지만 앞 그림의 (b)처럼 allocator는 alignment를 맞추기 위해 블록의 크기를 payload보다 크게 할 수도 있다.
Internal fragmentation은 수량화하기 쉽다. 단순하게 할당된 블록의 크기와 payload 간의 차를 모두 합산하면 된다. 따라서 internal fragmentation의 크기는 어느 순간에 재더라도 이전 요청들과 allocator의 구현 방식에만 의존한다.
External fragmentation 은 할당 요청을 만족하기 위한 총 메모리는 충분하지만, 여러 개로 쪼개져 있어서 크기를 만족하는 ‘단일’ 블록이 존재하지 않는 경우 발생한다. 예를 들어 앞 그림의 (e)에서 malloc(8)이었다면 분명 heap에는 총 8-word의 공간이 있지만 이 크기를 만족하는 단일 블록이 존재하지 않기 때문에 커널에게 요청해서 추가로 가상 메모리를 받지 않으면 요청을 수행할 수 없다.
External fragmentation은 internal fragmentation보다 훨씬 수량화하기 어렵다. 왜냐하면 이전 요청들의 패턴과 allocator의 구현 방식 뿐만 아니라 미래의 요청들의 패턴에도 의존하기 때문이다. 예를 들어 k개의 요청을 처리하고 나서 모든 free block이 4-word 크기인 상태라고 하면 이 heap은 external fragmentation에 의한 문제가 발생할까? 답은 앞으로 들어올 요청에 따라 다르다. 이후로 들어오는 요청이 모두 4-word 미만의 할당이라면 문제가 없겠지만 그보다 큰 할당 요청이 들어온다면 문제가 발생하게 된다.
External fragmentation은 수량화하기도 어렵고 예측도 힘들기 때문에 allocator들은 작은 블록 여러개보다는 큰 블록 몇 개를 유지하기 위해 여러 휴리스틱을 사용한다.
9.9.5 Implementation Issues
가장 단순한 allocator는 heap을 거대한 하나의 배열과 그 배열의 첫 바이트를 가리키는 포인터 p로 만들 수 있다. size 바이트를 할당하려면 malloc은 현재 p의 값을 저장하고, 포인터 p를 size만큼 위로 올린 다음 저장해 놓은 p를 caller에게 반환한다. free는 아무 것도 할 필요가 없다.
이 방법은 정말 단순해서 throughput은 극대화시키지만 그 어떤 메모리 블록도 재사용되지 않기 때문에 memory utilization 면에서는 최악이 된다. Throughput과 utilization의 균형을 잘 잡는 allocator는 다음 문제들을 고려해야 한다.
- Free block organization : free block들을 어떻게 추적할 것인가?
- Placement : 새로 할당할 때 어떤 free block을 골라서 할당하는 것이 가장 적절한가?
- Splitting: free block에 새로 할당했다면 기존 free block에서 할당하고 남은 부분은 어떻게 하는가?
- Coalescing: free된 블록에는 어떤 일을 해 주어야 하는가?
이 절의 나머지 부분에서는 이 문제들을 자세히 살펴볼 것이다. Placement, splitting, coalescing의 기본적인 기술은 여러 free block organization에도 적용되기 때문에, 이 문제들의 해결 방법을 implicit free list라고 하는 단순한 free block organization을 통해 소개한다.
9.9.6 Implicit Free Lists
Allocator는 allocated block과 free block을 구분하고 블록의 경계를 구분하기 위한 어떤 자료구조를 사용해야 한다. 대부분의 allocator는 블록 자체에 이 정보를 탑재하는데, 한 가지 간단한 방법은 아래 그림과 같다.
하나의 블록이 1-word짜리 헤더, payload, 그리고 추가적인 padding(선택)으로 구성된다. 헤더에는 블록의 크기(물론, 헤더 및 padding 포함)와 block의 상태(alloc인지, free인지)에 대한 정보가 들어 있다. 만약 우리가 double-word alignment를 적용한다면 헤더에서 블록의 크기는 항상 8의 배수이고 블록 크기를 나타내는 비트에서 LSB 3개 비트는 항상 0이 된다. 그래서 우리는 MSB 29개만 블록 크기 저장에 쓰고 남은 3개 비트에는 다른 정보를 저장한다.
3개 비트 중 LSB에 이 블록이 alloc 상태인지 free 상태인지를 저장하게 되는데, 예를 들어서 24바이트를 할당한다면 할당된 블록의 헤더에는
0x00000018 | 0x1 = 0x00000019
가 저장되어 있을 것이다.
헤더 다음으로 오는 것은 실제로 할당된 메모리 부분(payload)이고, 그 다음으로 오는 것은 padding이다.
크기도 정해지지 않고 사용하지 않는 부분인 padding을 붙이는 이유에는 여러 가지가 있을 수 있다. Externel fragmentation을 줄이기 위한 allocator의 전략의 일환일 수도 있고 align requirement때문에 필요한 부분일 수도 있다.
위 그림과 같은 블록 구조를 사용하면, 연속된 여러 블록들의 sequence로 heap을 구성할 수 있다. 아래 그림과 같다.
우리는 이를 implicit free list라고 부른다. 왜 implicit이냐면 free block들의 연결 관계가 각 블록의 헤더들의 블록 크기 정보에 내포되어 있기 때문이다. Allocator는 모든 블록을 탐색해서 간접적으로 free block들 전부를 돌아볼 수 있다.
여기서 특별히 표시된 end block이 있는 것을 주목하자. 위 그림에서는 헤더에 크기가 0이고 alloc 상태로 표시된 블록이 마지막에 존재한다. 9.9.12절에서 다루겠지만, 이렇게 하면 free block들을 병합하는 과정을 단순화할 수 있다.
Implicit free list의 장점은 단순하다는 것이지만, free list에서 searching이 오래 걸린다는 큰 단점이 있다. 새 블록을 할당하려면 heap에 있는 블록 전체의 수에 선형적으로 비례하는 탐색 시간이 걸리게 된다.
시스템의 alignment requirement와 allocator의 block format으로 인해 블록에 최소 크기가 생긴다는 것도 중요하다. 할당된 블록이든 free 블록이든 반드시 이 최소 크기보다 커야 한다. 예를 들어 2-word alignment를 사용하는 시스템에서는 한 블록의 크기는 반드시 2-word (8바이트) 단위여야 한다. 단 1바이트만 할당 요청을 하더라도 allocator는 2-word짜리 블록을 할당하게 된다.
9.9.7 Placing Allocated Blocks
Allocator는 k바이트 할당 요청을 받으면 free list를 탐색해서 크기가 충분한 블록을 찾는다. Allocator가 이 탐색 과정을 수행하는 방법은 placement policy에 달려 있는데, policy에는 first fit, next fit, best fit 등이 있다.
First fit은 free list의 시작부터 탐색해서 처음 나온 맞는 블록을 선택한다. Next fit은 first fit과 비슷하지만, 지난 탐색에서 찾았던 곳부터 탐색을 시작한다. Best fit은 모든 free block을 살펴보고 크기가 맞는 블록 중에 가장 작은 것을 선택한다.
First fit의 장점은 크기가 큰 블록은 리스트의 뒤쪽에 가게 되는 경향이 있다는 점이고, 단점으로는 작은 free block 조각들을 리스트 앞부분에 남겨 두게 되어 크기가 큰 블록의 탐색 시간을 늘리는 경향이 있는 것이다. Next fit은 Donald Knuth가 제안하였고, 직전에 크기가 맞는 free block을 찾았으면 그 블록의 나머지도 크기가 맞을 가능성이 높다는 아이디어로 제안되었다. First fit보다 실행 시간이 빠르지만 몇몇 연구는 next fit은 first fit보다 memory utilization에서 좋지 않다고 주장한다. Best fit은 first fit이나 next fit보다 memoy utilization은 낫지만 implitit free list같은 단순한 free list organization에서는 heap에서 불필요한 탐색을 많이 요구한다는 단점이 있다.
9.9.8 Splitting Free Blocks
Allocator가 크기가 맞는 free block을 찾았으면 그 free block의 얼마만큼을 사용할지에 대한 policy도 만들어야 한다. 한 가지 선택지는 free block 전체를 사용하는 것이다. 이렇게 하면 빠르고 간단하지만 단점은 internal fragmentation이 생긴다는 것이다. Placement policy가 성능이 좋아서 크기가 딱 맞는 걸 골라 준다면 어느정도 internal fragmentation은 봐줄 만 하지만, 크기가 딱 맞지 않다면 allocator는 free block을 두 개로 쪼개는 split 을 선택한다. 쪼개진 앞부분은 할당된 블록이 되고, 나머지는 새로운 free block이 된다.
9.9.9 Getting Additional Heap Memory
Allocator가 요청받은 크기에 맞는 블록을 찾을 수 업는 경우는 어떤 일이 발생할까. 한 가지 선택지는 물리적으로 인접해 있는 free block을 병합해서 더 큰 free block을 생성하는 것이고, 이렇게 해도 충분히 큰 free block을 만들 수 없거나 이미 모든 free block이 병합된 상태라면 allocator는 sbrk 함수로 커널에게 추가적인 heap memory를 요청한다. 추가된 메모리를 하나의 큰 free block으로 바꾸고 free list에 추가한 후 이 블록에 요청받은 블록을 할당한다.
9.9.10 Coalescing Free Blocks
Allocator가 할당된 블록을 free하면 새로 free된 블록과 인접한 다른 free block이 있을 수 있다. 이렇게 서로 인접한 free block들은 false fragmentation 이라는 현상을 일으킨다. 사용 가능한 수많은 free block들이 사용하기 힘든 작은 블록 조각들로 쪼개져 있는 상황이다. 아래의 fig 9.37과 9.38을 보면, 16바이트짜리 블록이 free되어서 payload가 3바이트인 두 free block이 인접해 있지만 쪼개져 있기 때문에 4바이트짜리 할당 요청이 들어오면 할당에 실패하게 된다.
False fragmentation을 방지하기 위해서 allocator는 coalescing 이라는 과정을 통해 인접한 free block들을 병합한다. Coalescing을 언제 수행해야 할 지에 대한 policy도 정해야 하는데, 블록이 free될 때마다 인접한 블록을 병합하는 immediate coalescing을 택할 수도 있고 미뤘다가 병합하는 deferred coalescing을 택할 수도 있다. 예를 들어 후자는 할당 요청이 실패했을 때 heap을 싹 탐색해서 가능한 모든 free block을 병합하는 식이다.
Immediate coalescing은 직관적이고 상수 시간에 수행될 수 있지만 블록이 반복적으로 alloc/free되는 패턴에서는 thrashing 과 같은 상황이 발생할 수 있다. 위 그림에서 3바이트를 alloc하고 free하고 alloc하고 free하고.. 를 반복하면 불필요한 splitting 과 coalescing을 반복하게 된다. 지금은 immediate coalescing만 고려하지만, allocator의 성능 향상을 위해서는 때로는 deferred coalescing을 선택해야 할 때도 있음을 알고 있자.
9.9.11 Coalescing with Boundary Tags
Allocator는 coalescing을 어떤 방식으로 구현할까? current block 을 free하려고 한다면 메모리 상에서 다음 블록과 병합하는 건 쉽고 효율적이다. 지금 보고 있는 블록의 헤더에는 다음 블록의 포인터가 있기 때문에 다음 블록이 free인지 alloc인지 바로 알 수 있기 때문이다. 해야 할 일은 현재 블록의 헤더에 블록 크기를 바꿔 쓰는 게 끝이고, 상수 시간에 수행될 수 있다.
메모리에서 이전에 있는 블록은 어떻게 할까? Implicit free list의 헤더만 가지고 할 수 있는 유일한 방법은 이전 블록의 위치를 기억하면서 current block이 나올 때까지 list 전체를 탐색하는 것이다. free 요청 하나하나가 heap 크기에 선형적으로 비례하는 시간 복잡도를 갖게 되는 것이다. Free list organization을 좀 더 정교하게 짜도 free 요청에서 탐색에 걸리는 시간은 절대 상수가 될 수 없다.
Knuth는 boundary tag 라는 기발한 아이디어로 이전 블록과의 병합을 상수 시간에 가능한 방법을 만들었다. 아래 그림과 같이 footer라고 불리는 boundary tag를 각 블록의 끝부분에 붙인다. Footer는 header를 복사한 것인데, 각 블록이 footer를 포함하고 있다면 allocator는 footer의 정보를 통해 현재 블록의 시작 지점과 이전 블록의 상태를 알아낼 수 있다.
앞뒤 블록의 경우의 수는 다음과 같이 4가지이다.
- 앞/뒤 블록 모두 alloc
- 앞 블록은 alloc, 뒷 블록은 free
- 앞 블록은 free, 뒷 블록은 alloc
- 앞/뒤 블록 모두 free
1번 경우는 현재 블록의 상태만 free로 바꿔 주면 된다 2번 경우는 현재 블록의 header와 다음 블록의 footer를 바꿔 주고, 3번 경우는 이전 블록의 header와 현재 블록의 footer를 바꿔 준다. 마지막으로 4번 경우는 앞 블록의 header와 뒷 블록의 footer를 바꿔 주면 된다. 모든 경우에서 coalescing이 상수 시간에 수행될 수 있다.
Boundary tag의 아이디어는 단순하면서 깔끔해서 여러 allocator과 free list organization들에 널리 사용된다. 하지만 잠재적인 단점도 존재하는데, 모든 블록에 header와 footer가 필요하기 때문에 작은 블록이 많이 있을 경우 overhead가 상당히 커진다. 예를 들어서 그래프 자료구조에서 한두개 word만 차지하는 node들을 계속 alloc하고 free하고 반복하는 경우 header와 footer의 overhead는 절반 가까이 된다.
다행히도 할당된 블록에는 footer가 없어도 되게 하는 좋은 최적화 방법이 있다. 왜 footer를 사용하는지를 되짚어 보면, 이전 블록의 상태를 알기 위함이었는데 이는 이전 블록이 free block인 경우에만 필요하다. 이전 블록의 상태만 현재 블록의 1비트를 써서 저장하면 free block만 footer를 남기고 allocated block은 footer 없이 사용할 수 있다.
9.9.12 Putting It Together : Implementing a Simple Allocator
이 절에서는 Implitcit free list와 immediate boundary-tag coalescing을 사용하는 간단한 allocator를 만들어 본다.
위 그림의 block format을 사용하고 최소 블록 크기는 16바이트이다. 그리고 앞 그림의 implicit free list를 조금 변형한 구조를 사용한다.
General Allocator Design
mem_init 함수는 가상 메모리를 본떠서 double-word aligned된 배열로 된 heap을 제공한다. 내용을 살펴보면, 할당된 가상 메모리의 시작과 끝을 나타내는 두 포인터 static char *mem_heap과 static char *mem_brk가 있다. mem_sbrk 함수는 시스템 함수 sbrk와 동일한 역할을 하는데, 음수 입력은 쳐내는 것 빼고 동일하다. mem_brk에 incr만큼 더하고 더하기 전 포인터를 반환한다.
heap의 맨 처음에는 사용하지 않는 1-word padding이 있고 그 다음으로 header와 footer로만 이루어진 8바이트짜리 alloc 상태의 prologue block가 있다. 초기화 과정에서 만들고 free되지 않는다. Prologue block 다음에는 앞으로 malloc과 free에 의해 생길 여러 블록들이 오게 된다.
heap의 마지막은 epilogue block인데, 헤더로만 구성된 크기가 0인 allocated 상태의 블록이다. Prologue/epilogue block은 나중에 coalescing에서 edge condition을 고려하지 않기 위한 장치이다. Allocator은 항상 prologue block을 가리키는 (static) global 변수 heap_listp를 갖는다.
Basic Constants and Macros for Manipulating the Free List
다음 코드는 앞으로 사용할 여러 상수들과 매크로들을 정의한 것이다.
먼저 word의 크기, double-word의 크기, 그리고 free block 크기의 초기값과 heap 확장의 기본 단위가 될 CHUNKSIZE의 값이 정의되어 있다. (line 2~4)
그 다음으로는 free list를 사용하기 위한 여러 매크로들이 정의되어 있다.
#define PACK(size, alloc) ((size) | (alloc))
PACK 매크로는 7비트 size와 1비트 alloc을 concat해서 header나 footer에 들어갈 1-word짜리 값을 만들어 준다.
#define GET(p) (*(unsigned int *)(p))
#define PUT(p, val) (*(unsigned int *)(p) = (val))
PUT과 GET 매크로는 주소 p를 받아서 그 주소의 값을 읽거나 값을 쓴다. p는 기본적으로 void * 자료형이기 때문에 `unsigned int *)로 casting이 반드시 필요하다.
#define GET_SIZE(p) (GET(p) & ~0x7)
#define GET_ALLOC(p) (GET(p) & 0x1)
이 두 매크로는 header나 footer의 주소 p를 받아서 size나 alloc의 정보를 추출한다.
#define HDRP(bp) ((char *)(bp) - WSIZE)
#define FTRP(bp) ((char *)(bp) + GET_SIZE(HDRP(bp)) - DSIZE)
#define NEXT_BLKP(bp) ((char *)(bp) + GET_SIZE(((char *)(bp) - WSIZE)))
#define PREV_BLKP(bp) ((char *)(bp) - GET_SIZE(((char *)(bp) - DSIZE)))
나머지 네 함수는 블록의 payload의 첫 바이트의 포인터(=bp)를 받아서 해당 블록의 header나 footer, 혹은 다음 블록/이전 블록의 bp를 반환하는 매크로이다.
size_t size = GET_SIZE(HDRP(NEXT_BLKP(bp)))```
다음 블록의 크기를 구할 때는 이렇게 매크로들을 조합해서 사용할 수 있다.
Creating the Initial Free List
가장 먼저 heap을 초기화하기 위해 mm_init 함수를 사용한다.
먼저 1-word padding과 prologue/epilogue block을 위해 4-word를 할당받는다. Prologue block은 크기가 2(header 1-word + footer 1-word)이고 alloc 상태이고, epilogue block은 크기가 0이고 alloc 상태이다. 그리고 나서 prologue block을 가리키는 포인터인 heap_listp를 설정해 준다.
그 다음은 CHUNKSIZE 크기의 첫 free block을 만드는 것이다.
먼저 alignment를 맞추기 위해서, 요청받은 크기 words가 홀수이면 +1을 해준다. 그리고 나서 mem_sbrk 함수를 이용해 heap을 확장한다.
다음으로는 새로 확장한 heap에 첫 free block을 할당하고 epilogue block을 새로 만들어 준다.
mem_sbrk의 반환값인 bp는 확장 이전 heap의 마지막 바이트+1을 가리키고 있다. 따라서 bp의 앞 바이트(이전 heap에서 epilogue block의 헤더가 있었던 곳)이 새 free block의 헤더가 위치할 장소가 된다. 즉, bp는 새 free block의 payload의 첫 바이트가 되는 것이다. 그래서 bp와 HDRP, FTRP 매크로를 이용해서 header와 footer, epilogue block을 만들어 준다.
마지막으로 이전 heap이 free block으로 끝났으면 새로 만든 free block과 병합을 해 주고 병합된 free block의 block pointer를 반환한다.
Freeing and Coalescing Blocks
Block pointer bp 받아서 블록을 free하고, 앞에서 다뤘던 경우 1~4에 따라 인접한 free block들과 병합한다.
mm_free에서는 free하려는 블록의 size를 구한 후 header와 footer를 free block의 것으로 바꿔 주고, coalesce 함수를 부른다.
coalesce서는 전/후 블록의 상태를 구한 후 4가지 경우 각각에 따라 알맞은 header와 footer로 바꿔 준다. 앞에서 free list를 처음 구성할 때 양 끝에 prologue, epilogue block을 박아 놓은 덕에 잘 일어나지도 않는 edge condition을 매번 고려하는 지저분한 코드가 되는 것을 막을 수 있었다.
Allocating Blocks
이제 프로그램에서 직접 사용할 malloc 함수를 만든다.
우선 요청받은 size를 alignment에 맞게 바꾸고 header와 footer가 들어갈 공간을 추가로 확보한다. size가 16바이트 미만이면 최소 블럭 크기인 16바이트로 만들어 준다.
place 함수로 free block list를 돌면서 적합한 block을 찾고 필요시 split 후 새로 할당된 블록의 주소를 반환한다. 찾을 수 없었다면 heap을 늘리고 그곳에 새로 할당해 준다.