[Malloc-lab] 동적 메모리 할당기(Dynamic Memory Allocator) 이해 과정

※ 이 글은 Why(왜)와 ?(물음표)를 바탕으로 작성한 글입니다. ※

※ 이해의 과정을 나열한 것이기 때문에 순서대로 천천히 읽는 것을 추천합니다. ※

 

목차

1. Dynamic Memory Allocation을 하는 이유

2. Dynamic Memory Allocator는 어떤 역할을 하기에 중요한가?

3. Dynamic Memory Allocator는 어디에서 memory를 가져와서 할당해주고, 반납해주는가?

4. 할당기와 가용리스트 확실히 하기 (명시적 vs 묵시적)

5. Dynamic Memory Allocator를 만드는 이유 👩‍💻

6. Dynamic Memory Allocator를 실제로 구현할 때 어떤 것들을 중요하게 고려해야하는가?

7. Dynamic Memory Allocator 만들기

 

1. Dynamic Memory Allocation을 하는 이유

이 과제의 의도는 무엇인가? 이 프로그램을 왜 구현하는지 모르면 과제를 하던 도중 malloc hell에 빠져들 것만 같았다.

일단 동적 메모리 할당을 왜 하는지에 대한 생각부터 해봐야겠다.

먼저 가정을 하자. 나는 태초의 천재 프로그래머이고(ㅎ)👩‍💻 일단 귀찮아서 최대 배열 크기를 갖는 정적 배열로 프로그램을 만들어놨다. 그런데 일단 크게 만들어놨기에 프로그램이 터질 일은 줄어들지만, 정적 메모리 할당은 메모리 관리가 어려워진다.

 

정적 메모리 할당을 할 경우 메모리 관리에 여러가지의 어려움이 있다.

- 선언된 배열 요소의 수가 사용된 요소의 수보다 많을 수도 있고, (메모리 낭비)

- 선언된 배열 요소의 수가 사용된 요소의 수보다 적을 수도 있고, (메모리 부족)

- 배열 선언할 때 배열 길이에 변수를 설정하면 에러가 발생

// 선언된 배열의 요소의 수가 사용된 요소의 수보다 많은 경우(메모리 낭비)
// 컴파일 타임에 미리 지정시 메모리 낭비 발생

int array[5]; // 선언된 배열 요소의 수: 5개 (20byte)
array[0] = 10, array[1] = 20, array[2] =30; // 사용된 배열 요소의 수: 3개 (12byte)

// 선언된 배열 요소의 수가 사용된 요소의 수보다 적을 수도 있고, (메모리 부족)
// 컴파일 타임에 미리 확정시 메모리 부족 발생

int array[2]; // 선언된 배열 요소의 수: 2개 (10byte)
array[0] = 10, array[1] = 20, array[2] =30; // 사용된 배열 요소의 수: 3개 (12byte)

// 배열 선언시 배열 길이에 변수를 설정한 경우 에러 발생
// 프로그래머가 필요한 메모리 크기를 예측할 수 없다. 
int a = 5;
int array[a]; // 배열 선언 시 배열 a를 배열 길이로 사용
void init(int a){
    int array[a]; // 배열 선언 시 함수의 인자(지역 변수) a를 배열 길이로 사용
}

Reference: 동적 메모리 할당이 필요한 이유 https://codedragon.tistory.com/7123

 

천재 프로그래머는 정적 메모리 할당으로 찾기 힘든 오류에 스트레스를 받고 있다. 😭

아무리 천재 프로그래머도 신은 아니기에 프로그램 실행 시 메모리가 얼마나 필요할지 가늠하기 어렵다.

정적 메모리 할당은 프로그램 컴파일(Complie)시 메모리(stack)에 얼마만큼의 크기로 할당을 해야하는지 결정되기 때문에, 컴파일 이후 크기가 변경될 수 없다. 메모리 부족, 에러 등과 같이 문제가 발생했을 때, 메모리를 더 크게 할당해주고 다시 컴파일을 해줄 수 있지만 이 과정 자체가 software engineer의 생산성을 떨어뜨리는 일이다.  

이 메모리 녀석을 어떻게 하면 메모리 낭비, 메모리 부족, 에러 없이 할당할 수 있을까?

 

🤔 정적으로 말고 동적으로 내가 원하는 시점에 원하는 크기만큼 메모리를 할당하면 괜찮을거 같은데?

💡 그리고 메모리 사용이 끝나면 언제든지 해제해주면 메모리가 모자랄 일이 줄어들거 같은데?

 

그렇다. 메모리 관리의 어려움을 해결하기 위해서 런타임(Runtime)시 메모리(heap)에 데이터를 동적으로 할당한다.

그게 동적 메모리 할당(Dynamic memory allocation, 줄여서 malloc)이다. 메모리의 최대 크기는 사용가능한 가상 메모리의 양에 의해서만 제한된다.

동적 메모리 할당의 예시

🏷️요약 💥

정적 할당 => 컴파일시 => 스택에 메모리 할당 / 프로그램 종료시까지 할당된 상태 유지

동적 할당 => 런타임시 => 힙에 메모리 할당 & 해제

즉, 동적 메모리 할당을 하는 이유는 프로그램을 실행시키 전에 자료구조의 크기를 알 수 없는 경우가 많기 때문이다.

 

2. Dynamic Memory Allocator는 어떤 역할을 하기에 중요한가?

역할을 말하기 전에, Q. 동적 메모리 할당기가 뭐냐고?

동적 메모리 할당기는 프로세스 가상 메모리 영역을 관리하는데, 이 가상 메모리 영역을 힙(heap)이라고 한다. 천재 프로그래머는 동적 메모리 할당기를 사용해 프로그램이 돌아가는 시간(런타임)에 추가 가상 메모리를 얻는다.

 

Q. 가상 메모리가 뭐냐고?

A. 가상 메모리 또는 가상 기억 장치는 메모리 관리 기법의 하나로, 기계에 실제로 이용 가능한 기억 자원을 이상적으로 추상화하여 사용자들에게 매우 큰 메모리로 보이게 만드는 것을 말한다. 각 프로그램에 실제 메모리 주소가 아닌 가상의 메모리 주소를 주는 방식이다.

[Malloc-lab] 가상메모리(Virtual Memory)

 

다시 돌아가서, Q. 동적 메모리 할당기는 어떤 역할을 하기에 중요한가?

1. 초기에 설정된 힙 영역이 있다. 해당 영역에서 메모리가 할당이 되기도 해제되기도 한다. 이 과정에서 힙 영역 중간 중간에 사용가능한 공간들이 생기게 된다.

2. 특정 사이즈의 메모리 할당 요청시 그때 그때(Runtime) 메모리 곳곳에 있는 할당 가능한 블록들을 탐색하며 요청받은 사이즈에 맞는 가용블록을 찾아준다. 혹은 가용블록이 없으면 힙 영역을 위로 확장시켜서 새로운 주소를 할당해준다.

즉, 런타임(Runtime)시 메모리(heap)에 데이터를 동적으로 할당하는 과정에서 할당 뿐만 아니라 다른 일(메모리 할당, 해제, 알맞은 가용블록 찾기, 가용블록 없으면 힙 확장 새 주소 할당 등등)을 많이 함.

 

🏷️요약 💥

정의 =>  Heap(힙)이라는 가상 메모리 영역을 관리

역할 => 메모리 할당, 해제, 알맞은 가용블록 찾기, 가용블록 없으면 힙 확장 새 주소 할당 등등

 

3. Dynamic Memory Allocator는 어디에서 memory를 가져와서 할당해주고, 반납해주는가?

힙에 대한 설명 https://bo5mi.tistory.com/159

 

힙이 미초기화된 데이터 영역(BSS 영역) 직후에 시작해서 위쪽으로(높은 주소 방향으로) 커지는 메모리 영역/ 커널은 힙의 꼭대기를 가리키는 변수 brk(break)를 사용한다.

Application이 사용하는 메모리 영역은 여러 segement로 범주화되어 관리된다. (데이터 세그먼트에 관한 정리)

힙 영역(Heap segment)은 다양한 사이즈의 할당된 블록(allocated block)과 가용 블록(free block)들로 이루어져 있다.

Application이 Dynamic memory allocator에게 메모리 할당을 요청하면,

1) 적당한 free block을 찾아서 이 free block에 대한 pointer를 application에 반환해주고 해당 free block을 allocated 되었다고 기입해둔다. 

2) 만약 application이 요청하는 사이즈의 free block을 찾을 수 없다면, sbrk라는 system call를 통해서 시스템으로부터 더 많은 메모리를 할당받는다. 이를 통해 적절한 사이즈의 free block을 확보하고, 이에 대한 포인터를 application에게 반환해준다. 

* 참고로 sbrk를 호출하면 brk 포인터를 위로 올리거나 낮춤으로써 heap memory를 증가시키거나 감소시킬 수 있다. 

 

🏷️요약 💥

사실 위에 설명한 '어떤 역할을 하는가'와 반복적인 얘기이다. 

Dynamic Memory Allocator는 Heap(힙=가상 메모리 영역)에서 memory를 가져와서 할당해주고, 반납해준다.

 

4. 할당기(Allocator)와 가용 리스트(free list) 확실히 하기 (명시적 vs 묵시적)

- 명시적 '할당기'(Explicit Allocator): 할당된 블럭을 명시적으로 해제(free)해줘야 하는 할당기 ex) C의 malloc, free

- 묵시적 '할당기'(Implicit Allocator): JAVA의 Garbage collector처럼, 할당된 블록이 더이상 사용되지 않으면 이를 감지해서 해제해주는 할당기(C에는 없음)

 

- 명시적 '가용리스트'(Explicit Free List): 가용(free)블럭들이 '묵시적 또는 암묵적'으로 서로 연결되어있는 가용리스트. 묵시적이란 뜻은 겉으로 드러나게 다른 free 블록과 연결되어있는 것은 아니지만 간접적으로 블록의 헤더에 사이즈가 명시되어있기 때문에 연결되어있다고 볼 수 있음

- 묵시적 '가용리스트'(Implicit Free List): 가용(free)블럭의 payload는 어차피 프로그램에 의해서 필요하지 않으니까 이 자리에 이전 블록과 다음 블록을 가리키는 포인터를 포함하여, '명시적 또는 직접적'으로 다른 가용 블록과 연결되어 있는 가용리스트 

 

🏷️요약 💥

요약할게 없다. 

명시적과 묵시적에 눈이 멀어 할당기와 가용 리스트를 헷갈리지 말자.

 

5. Dynamic Memory Allocator를 만드는 이유 👩‍💻

내가 궁금한 것. 이 과제의 의도는 무엇인가? 동적 메모리 할당기를 왜 만드는데?

조원들과 얘기를 해본 결과 과제의 숨겨지거나 명확한 이유는 없는 것 같다. 

일단 해봄으로써 malloc이 어떻게 돌아가고 이 과정에서 구체적인 개념을 확인할 수 있는지에 대해 알고...

 

정말 literally 이정도라고 생각 중 => Application이 메모리를 요청하면 malloc을 통해 메모리를 할당 받고, free를 통해 메모리를 반환한다. 이번 프로젝트에서는 CMU(카네기 멜론 대학교) 과제 중 하나인 malloc lab을 직접 구현해본다. malloc을 C언어로 구현하면서, C언어 포인터의 개념, gdb 디버거 사용법 등을 익혀본다.

 

하지만, 여기서 멈추긴 애매하다.

더 deep하게 생각한 부분은 가상 메모리의 동작 방식에 대해 생각해보기 위함 아닐까?

결국 동적 메모리 할당기는 힙을 관리하는 역할을 하고, 힙은 가상 메모리의 영역이기 때문에 동적 메모리 할당기의 동작 방식을 이해함으로써 가상 메모리의 동작 방식을 수월하게 이해할 수 있지 않을까? 이에 대해 고민해볼 필요가 있을 것 같다.. 아직 뇌피셜이다...!

 

🏷️요약 💥

일단 해라.

 

6. Dynamic Memory Allocator를 실제로 구현할 때 어떤 것들을 중요하게 고려해야하는가?

Dynamic memory allocator 성능을 측정하는 대표적인 지표는 memory utilization과 throughput이다.

- memeory utilization: heap segment를 낭비하는 공간 없이 application이 필요한 데이터를 얼마나 꽉 채워서 썼는가 

- throughput: 얼마나 빨리 applictaion의 allocate/free 요청을 처리해줄 수 있는가 

 

memory utilization과 throughput에 영향을 끼치는 중요한 구현 요소는 다음과 같다.

1. free block organization

- heap segment는 array of bytes이고 이 array가 다양한 size의 free block과 allocated block으로 뒤섞여 채워져있다. 

- 이런 상황에서 어떤 방식으로  free block들을 축적 관리할 것인가에 관한 것이 free block organization이다. 

- free block들을 일종의 list 형태로 추적 관리하는 방식이 크게 3가지가 있는데, implicit free list(묵시적 가용 리스트), explicit free list(명시적 가용 리스트), segregated free list(분리 가용 리스트)가 있다. 

- 어떤 종류의 free block organizations을 채택하느냐에 따라 free block format, placing 방식, spliting 방식, coalescing 방식이 모두 달라질 수 있다.

 

2. placing

- application으로부터 memory를 할당해달라는 요청을 받았을 때, dynamic memory allocator는 위에서 결정된 free block organizations에 따라 사용하고 있는 free list에서 적절한 free block을 찾아야 한다. 이 때 이 free block을 찾는 방식에 관한 것이 placing이다. 적절한 free block을 찾는 방식으로 크게 3가지 방식이 있는데, first-fit, next-fit, best-fit이 있다. 

3. splitting

- fit한 free block을 찾고 나서 해당 블록을 allocated로 표식해놓고 application한테 해당 블록에 대한 pointer를 바로 반환할 수 있다.

- 하지만 만약 해당 free block이 application이 요청한 사이즈보다 훨씬 클 경우 이 block을 통째로 application에게 주면 낭비가 된다. (internal fragmentation; 내부 단편화)

- 이 낭비를 줄이기 위해서, free block을 적절히 2개의 블록으로 쪼개서 필요한 만큼만 allocated 처리하고 나머지 block은 free 상태로 처리해놓을 수 있다.

 

4. coalescing

- splitting 이후 생성된 free block의 앞 뒤로 만약 또 다른 free block이 존재한다면 블록들을 합쳐놓는게 좋을 수 있다. 

- coalescing을 하는 명확한 이유는 외부 단편화를 막기 위함이다. 만약 heap에 크기가 4인 free block 2개가 있다. application이 memory 할당을 요청한 사이즈가 5라면 free list에서 fit한 크기의 free block을 찾지 못해 NULL을 반환하거나 sbrk 시스템 콜을 이용해서 불필요하게 늘려야 할 수 있다. 

- 이런 경우를 막기 위해 연속적으로 존재하는 free block을 미리 합쳐놓는 작업을 할 수 있는데, 이를 coalescing이라고 한다.

 

7. Dynamic Memory Allocator 만들기 

 Implicit Free list(묵시적 가용 리스트)

묵시적 가용 블록의 구조

 Implicit Free list(묵시적 가용 리스트)를 사용하는 malloc을 구현하기 위해 어떤 부분이 고려되어야하는지 확인해보자.

1. 힙 영역의 시작과 끝 부분 및 각 가용블록의 경계표시, 블록의 사이브, 할당여부 표기법 

2. 할당가능 블록 탐색 및 배치 

3. 할당 시 가용리스트 분할 

4. 할당 불가능시에 추가 힙 영역 획득 

5. 인접한 가용리스트끼리의 연결 

 

1. 힙 영역의 시작과 끝 부분 및 각 가용블록의 경계표시, 블록의 사이브, 할당여부 표기법

Implicit Free list(묵시적 가용 리스트)의 불변하는 형식

힙 영역은 Prologue block과 Epiloge block으로 경계가 구분된다.

각각의 블록은 블록 사이즈 정보와 가용여부가 표기되어있는 header와 footer로 경계가 구분된다.

 

- header: 블록의 크기(size)와 할당 여부(allocate)를 저장한다.

- payload: 할당된 블록에만 값이 들어있다.

- padding: double word 정렬을 위해 optional하게 존재

- footer: 경계 태그로 사용되며, header의 값이 복사되어 있다. 블록을 반환할 때 이전 블록을 상수 시간 내에 탐색할 수 있도록 하는 장치(footer가 없으면 모든 블록의 size 정보가 다르기에 이전 header를 찾아내기 위해서 힙의 시작점부터 순차적으로 탐색해야하는 불편함이 있다.)

 

2. 할당가능 블록 탐색 및 배치

묵시적 가용 리스트의 경우 가용리스트를 따로 관리하지 않고, 때마다 요청 블록 size와 맞는 블록을 탐색해서 찾는다.

방법은 다양하지만 3가지의 방법이 기술되어있다. => First fit/Next fit/Best fit

 

First Fit: 힙 시작점부터 탐색한다. 요청에 맞는 첫 번재 블록 발견시 채택하는 아이디어

Next Fit: 마지막 가용블록을 발견한 지점부터 탐색을 시작하면 확률적으로 유리하다는 아이디어

Best Fit: 전체를 탐색하는 아이디어 => 힙 전체를 검색해야하는 단점이 있지만, 가장 알맞은 사이즈의 블록을 찾을 수 있기에 메모리 이용도는 다른 방법보다 우수

 

3. 할당시 가용리스트 분할

발견한 가용 블록이 크기가 큰 경우 두 가지 옵션이 있다. 

1. 그대로 채택한다.

2. 필요한 부분만 잘라서 쓰고, 나머지 부분을 가용블록을 변경한다.

(1의 경우 내부 단편화에 조금 더 취약하다.)

 

4. 할당 불가능시에 추가 힙 영역 획득

기존 힙 영역에 할당 가능한 가용블록이 없는 경우 힙 영역을 상단으로 확장시켜서 추가로 메모리를 할당 받는다.

mem_sbrk 함수를 활용한다. mem_sbrk 함수는 heap 영역의 최상단에 위치한 ptr를 incr만큼 이동시키는 함수이다. 

 

5. 인접한 가용 리스트끼리의 연결

4가지 case가 있다.

case 1: 직전, 직후 블록이 모두 할당

case 2: 직전 블록 할당, 직후 블록 가용

case 3: 직전 블록 가용, 직후 블록 할당

case 4: 직전, 직후 블록 모두 가용

---

1) memlib.c 메모리 시스템 모델 

(memlib.c 기본적으로 제공되기에 실제 코드로 구현할 필요는 없다.)

=> sbrk 함수를 잘 이해하는 것은 중요하다. 

/* private variables */
static char *mem_start_brk;  /* points to first byte of heap, 힙의 첫 바이트를 가리키는 변수 */
static char *mem_brk;        /* points to last byte of heap, 힙의 마지막 바이트를 가리키는 변수. 여기에다가 sbrk 함수로 새로운 사이지의 힙을 할당받는다.  */
static char *mem_max_addr;   /* largest legal heap address, 힙의 최대 크기(20MB)의 주소를 가리키는 변수 */ 

/* 
 * mem_init - initialize the memory system model
   최대 힙 메모리 공간을 할당받고 초기화해준다.
 */
void mem_init(void)
{
    /* allocate the storage we will use to model the available VM */
    // config.h에 정의되어 있음, #define MAX_HEAP (20*(1<<20)) : 20971520bytes == 20 MB
    // 먼저 20MB만큼의 MAX_HEAP을 malloc으로 동적할당해온다. 만약 메모리를 불러오는데 실패했다면 에러 메세지를 띄우고 프로그램을 종료한다.
    // 그 시작점을 mem_start_brk라 한다.
    // 아직 힙이 비어 있으므로 mem_brk도 mem_start_brk와 같다.
    if ((mem_start_brk = (char *)malloc(MAX_HEAP)) == NULL) {
	fprintf(stderr, "mem_init_vm: malloc error\n");
	exit(1);
    }
    mem_max_addr = mem_start_brk + MAX_HEAP;  /* max legal heap address */
    mem_brk = mem_start_brk;                  /* heap is empty initially */
}

/* 
 * mem_sbrk - simple model of the sbrk function. Extends the heap 
 * by incr bytes and returns the start address of the new area. In
 * this model, the heap cannot be shrunk.
 * byte 단위로 필요 메모리 크기를 입력받아 그 크기만큼 힙을 늘려주고, 새 메모리의 시작 지점을 리턴한다.
 * 힙을 줄이려 하거나 최대 힙 크기를 넘어버리면 리턴한다.
 * old_brk의 주소를 리턴하는 이유: 새로 늘어난 힙의 첫번째 주소이기 때문
 */
void *mem_sbrk(int incr) // incr => 바이트 형태로 입력받음
{   
    char *old_brk = mem_brk; // 힙 늘리기 전의 끝 포인터를 저장한다. 

    // 힙이 줄어들거나 최대 힙 사이즈를 벗어난다면
    // 메모리 부족으로 에러처리하고 -1을 리턴한다.
    if ( (incr < 0) || ((mem_brk + incr) > mem_max_addr)) {
	errno = ENOMEM;
	fprintf(stderr, "ERROR: mem_sbrk failed. Ran out of memory...\n");
	return (void *)-1; // 리턴값이 void*여야해서 형변환
    }
    mem_brk += incr;    // incr(요청된 용량)을 mem_brk에 더해준다. 
    return (void *)old_brk; // old_brk를 리턴하는 이유는 새로 늘어난 힙의 첫번째 주소이기 때문이다.
}

전역변수부터 살펴보자.

static char *mem_start_brk;

: 힙의 첫 바이트를 가리키는 변수 
static char *mem_brk;

: 힙의 마지막 바이트를 가리키는 변수. 여기에다가 sbrk 함수로 새로운 사이지의 힙을 할당받는다.  
static char *mem_max_addr; 

: MAX_HEAP의 끝자리를 가리킨다. 이 이상으로는 할당할 수 없다.

 

mem_init

- 힙에 가용한 가상 메모리를 큰 더블 워드로 정렬된 바이트의 배열로 모델한 것이다.

- 할당기를 초기화하고, 성공하면 0을, 아니면 -1을 반환한다.

 

mem_sbrk

- incr(할당 요청이 들어왔을 때, 요청된 용량)가 들어왔을 때, 이것이 MAX_HEAP을 초과하지 않으면 추가로 mem_brk를 할당 요청 용량만큼 옮긴다. (할당 요청이 들어오기 전에 mem_brk의 위치는 old_brk였다.) 만약 용량의 크기가 음수이거나, MAX_HEAP을 초과하면 error 메세지를 반환한다. 

컴퓨터 시스템 p.823, 그림 9.41

예를 들어, 현재 mem_brk가 10의 위치라면 mem_sbrk(10)을 했을 경우 mem_brk의 값은 20이 되고, 10만큼 Heap의 크기가 증가한다. 그리고 mem_sbrk는 old_brk인 10을 리턴한다. 이때, old_brk를 리턴하는 이유는 새로 늘어난 힙의 첫번째 주소이기 때문이다. 만약 힙의 최대 크기 max_addr이 20인데 사용자가 30을  incr(할당 요청이 들어왔을 때, 요청된 용량)하라고  요청하면 -1 포인터를 리턴한다.

 

2) mm.c

① 가용 리스트 조작을 위한 기본 상수 및 매크로 정의

=> 매크로를 잘 이해해야 뒤에가 편하다. 

여기서, 매크로란 동적 할당기(malloc)을 만들 때 자주 쓰는 기능들을 미리 만들어 놓고 가져다 쓰는 것으로 잘 이해해야한다.

/* single word (4) or double word (8) alignment */
#define ALIGNMENT 8

/* rounds up to the nearest multiple of ALIGNMENT */
// size보다 큰 가장 가까운 ALIGNMENT의 배수로 만들어준다 => 정렬
// size = 7: (00000111 + 00000111) & 11111000 = 00001110 & 11111000 = 00001000 = 8
// size = 13: (00001110 + 00001110) & 11110001 = 00010000 = 16
// 1 ~ 7 bytes: 8 bytes
// 8 ~ 16 bytes: 16 bytes
// 17 ~ 24 bytes: 24 bytes
#define ALIGN(size) (((size) + (ALIGNMENT-1)) & ~0x7)

// 메모리 할당 시 기본적으로 header와 footer를 위해 필요한 더블워드만큼의 메모리 크기
// size_t: 해당 시스템에서 어떤 객체나 값이 포함할 수 있는 최대 크기의 데이터 
#define SIZE_T_SIZE (ALIGN(sizeof(size_t)))

/* Basic constants and macros */
#define WSIZE 4             /* Word and hearder/footer size (bytes 단위) */
#define DSIZE 8             /* Double word size (bytes 단위) */
#define CHUNKSIZE (1<<12)   /* Extend heap by this amount (bytes), heap의 초기 사이즈 설정용 */

#define MAX(x, y) ((x) > (y)? (x) : (y))

/* Pack a and allocated bit into a word */
// PACK 매크로: 크기와 할당 비트를 통합해서(or 연산자 활용) header와 footer에 저장할 수 있는 값 리턴
// header 및 footer 값 (size + allocated) 리턴
// 더블워드 정렬로 인해 size의 오른쪽 3~4자리는 비어있다.
// 이 곳에 0(freed), 1(allocated) flag를 삽입한다. 
#define PACK(size, alloc) ((size) | (alloc))

/* Read and write a word at address p */
// GET 매크로: 주소 p가 참조하는 워드를 읽는 함수 
// PUT 매크로: 주소 p가 가리키는 워드에 val을 저장하는 함수
#define GET(p)          (*(unsigned int *)(p))
#define PUT(p, val)     (*(unsigned int *)(p) = (val))

/* Read the size and allocated fields from address p */
// GET_SIZE 매크로: GET으로 읽어온 p 워드의 사이즈 정보를 읽어오는 함수
// 작동 원리 => 비트연산 활용, p는 (size + allocated) 값을 가지고 있는 헤더이기에 4바이트(32비트) 중 29비트까지는 size 정보, 나머지 3비트는 allocated 정보, & 연산 활용하여 블럭의 사이즈 값만 리턴 가능
// & ~0x7 => 0x7: 0000 0111 ~0x7: 1111 1000이므로 ex) 1011 0111 & 1111 1000 = 1011 0000 : size 176bytes

// GET_ALLOC 매크로: 사이즈 정보를 무시한 채 할당 여부를 나타내는 맨 뒷자리만 확인하는 함수
// & 0x1 => ex) 1011 0111 & 0000 0001 = 0000 0001 = 1: Allocated 
#define GET_SIZE(p)     (GET(p) & ~0x7)
#define GET_ALLOC(p)    (GET(p) & 0x1)

/* Given block ptr bp, comput address of its header and footer */
// HDRP 매크로: bp가 속한 블록의 헤더를 알려주는 함수
// FTRP 매크로: bp가 속한 블록의 풋터를 알려주는 함수
// 블록 포인터 bp를 인자로 받아 블록의 header와 footer의 주소를 반환한다. 
// 포인터가 char* 형이므로, 숫자를 더하거나 빼면 그 만큼의 바이트를 뺀 것과 같다.
// WSIZE 4를 뺀다는 것은 주소가 4byte(1 word) 뒤로 간다는 뜻. bp의 1word 뒤는 헤더. 
#define HDRP(bp)        ((char *)(bp) - WSIZE)
#define FTRP(bp)        ((char *)(bp) + GET_SIZE(HDRP(bp)) - DSIZE)

/* Given block ptr bp, comput address of next and previous blocks */
// 블록 포인터 bp를 인자로 받아 이후와 이전의 블록 주소를 리턴한다.
// NEXT_BLKP 매크로: 지금 블록의 bp에 블록의 크기(char*이므로 word 단위)만큼을 더한다.
# define NEXT_BLKP(bp)  ((char *)(bp) + GET_SIZE(((char *)(bp) - WSIZE)))   // (char *)(bp) + GET_SIZE(지금 블록의 헤더값)
# define PREV_BLKP(bp)  ((char *)(bp) - GET_SIZE(((char *)(bp) - DSIZE)))   // (char *)(bp) - GET_SIZE(이전 블록의 풋터값)

/* global variable & functions */
static char *heap_listp;    // 항상 prologue block을 가리키는 정적 전역 변수 설정

// 기본 함수 선언
int mm_init(void);
void *mm_malloc(size_t size);
void mm_free(void *bp);
void *mm_realloc(void *ptr, size_t size);

// 추가 함수 선언
static void *extend_heap(size_t words);
static void *coalesce(void *bp);
static void *find_fit(size_t asize);
static void place(void *bp, size_t newsize);

#define ALIGNMENT 8

#define ALIGN(size) (((size) + (ALIGNMENT-1)) & ~0x7)

- size보다 큰 가장 가까운 ALIGNMENT의 배수로 만들어준다 => 정렬

예를 들면, 

- size = 7: (00000111 + 00000111) & 11111000 = 00001110 & 11111000 = 00001000 = 8

- size = 13: (00001110 + 00001110) & 11110001 = 00010000 = 16

Q. 왜 8자리로 표현하는가?

컴퓨터의 최소 저장 단위는 1바이트이기 때문이다. (1byte = 8bit)

우리가 1이라는 수를 저장하기 위해 1을 입력하든 0001을 입력하든 000000001을 입력하든 1이다.

하지만, not연산을 하는 경우나 수를 뒤집어야하는 경우에는 경우가 달라진다. 

not 연산의 경우 0이 1으로 바뀌고, 1이 0으로 바뀌기 때문에 결과값이 달라질 수 있다. 

 

#define SIZE_T_SIZE (ALIGN(sizeof(size_t)))

- size_t는 unsigned int로 4바이트이다. 

- ALIGN(sizeof(4바이트)) => 8

- 그러므로, 이 코드에서 SIZE_T_SIZE는 계속 8이다.

현재 대부분의 x86 컴퓨터는 32비트 또는 64비트 운영체제를 사용하고 있다.
요즘은 ARM에서도 64비트를 사용 중이다. c언어의 변수의 크기는 구동 환경에 따라 다르다. 
보편적인 경우에 int형의 크기는 4바이트 (32비트)라고 알 것이다. 
이는 32비트의 환경에서만 적용된다. 즉, 대부분의 변수는 동작 환경에 따라 크기가 달라진다.

하지만 size_t 의 경우에는 다르다.
보통 헤더 파일에 정의가 되어 있는데, size_t는 4바이트의 크기를 가지고 있다 (32비트 unsigned int). 이것은 환경이 바뀌어도 항상 4바이트로 고정이 되어 있다. 그래서 어디서든 4바이트의 크기(unsigned int)를 가지는 변수를 선언하고 싶을 때는 size_t로 선언하면 된다. 이와 비슷하게 ssize_t 라는 변수도 있는데, 이것은 signed int 형태를 가진다.

 

#define WSIZE 4/DSIZE 8/CHUNKSIZE (1<<12)

- 1워드(word)는 4byte, 2워드(double word)는 8byte이기 때문에 4와 8을 WSIZE, DSIZE라고 size 상수를 정의함.

- CHUNKSIZE (1<<12)는 1을 왼쪽으로 12칸 쉬프트 연산한 결과가 나온다. (2^12)

- Q. 왜 2의 12승을 만드는가 하면 뒤에서 나오지만 (CHUNKSIZE/WSIZE)를 하면 (2^12/2^10)으로 2^2인 4가 되는데 extend_heap() 함수 할 때 인자로 4를 넘겨줘야 최소 alignment 16바이트 블럭을 만들게된다. (헤더 4 + 페이로드 정렬 8 + 푸터 4 = 16바이트) 

Q. 왜 하필 2의 12승(4096)인지 (다른 말로 왜 하필 extend_heap할 시 2^12승, 4kib만큼의 힙을 요청하는지)

• 4 KiB만큼의 heap을 요청하는 이유는 1 page가 4 KiB이기 때문이라고 생각하시면 될 것 같습니다. 컴퓨터 입장에서 페이지는 메모리를 묶어서 다루는 가장 자연스러운 단위입니다. 추후 PintOS를 구현하면서 OS가 어떻게 하드웨어와 발을 맞춰 페이지 단위로 메모리를 관리하는지 배우게 될 것입니다.

 

• 그렇다면 1 page는 왜 4 KiB일까요? 컴퓨터가 사용할 수 있는 메모리는 정해져 있습니다. 따라서 페이지가 너무 작으면 페이지의 개수가 매우 많아서 이들을 관리하는 데 불필요하게 많은 자원을 써야 할 것이고, 페이지가 너무 크면 페이지를 사용하지 않고 남기는 부분이 많아 메모리가 낭비될 것입니다. 따라서 컴퓨터를 설계할 때 적절한 페이지 크기를 골라야 합니다. 페이지를 사용한 최초의 CPU인 인텔 80386은 1 page = 4 KiB를 골랐고, 이 크기가 x86 아키텍처에 남아 지금까지 유지되어 왔다고 생각할 수 있겠습니다.

(https://stackoverflow.com/q/11543748 이 내용을 참고했습니다.)

 

=> KiB는 키비바이트(영어: Kibibyte, KiB) 또는 킬로 이진 바이트(Kilo binary byte)는 정보나 컴퓨터 저장장치의 단위이다.

1 킬로 이진 바이트 = 210 바이트 = 1,024 바이트

 

#define MAX(x, y)     ((x) > (y) ? (x) : (y))

- 삼항 연산자 문법에 따라 x가 y보다 크면 x를 return, 작으면 y를 return 

 

#define PACK(size, alloc)     ((size) | (alloc))

- size(크기)와 alloc(할당 비트)를 통합해서 header와 footer에 저장할 수 있는 값을 리턴함.

- 즉, size와 alloc을 or 연산자로 합치는 함수이다. 

- 더블워드 정렬로 인해 size의 오른쪽 3~4자리는 비어있다. 이 곳에 0(freed), 1(allocated) flag를 삽입한다. 

 

#define GET(p)         (*(unsinged int *)(p))

- 주소 p가 참조하는 워드를 읽는 함수

- 그런데 주소의 값을 읽어오는거면 *p를 하면 되는데 왜 (*(unsigned int *)(p)) 이런 짓을 하냐?

- p의 타입은 대게 void형인데 (void *) void형 포인터를 *로 역참조 할 수 없다. 

- 왜냐면 int *p처럼 p가 int형인지, long형인지 정의가 안 되어있기 때문에 void 포인터 값을 읽으려면 형변환(캐스팅)을 시켜줘야한다. int *(p)로 void형에서 int형으로 바꿔주고 다시 * 역참조를 해서 p 주소에 있는 값을 읽어온다. 

 

#define PUT(p, val)   (*(unsinged int *)(p) = (val))

- 주소 p가 가리키는 워드에 val을 저장하는 함수

- 위와 같이 똑같이 형변환을 해주고 역참조를 해서 p 주소에 있는 값에 val를 저장한다. 

 

#define GET_SIZE(p) (GET(p) & ~0x7)

- GET으로 읽어온 p 워드의 사이즈 정보를 읽어오는 함수

- 작동 원리 => 비트연산 활용, p는 (size + allocated) 값을 가지고 있는 헤더이기에 4바이트(32비트) 중 29비트까지는 size 정보, 나머지 3비트는 allocated 정보, & 연산 활용하여 블럭의 사이즈 값만 리턴 가능

- & ~0x7 => 0x7: 0000 0111 ~0x7: 1111 1000이므로 ex) 1011 0111 & 1111 1000 = 1011 0000 : size 176bytes

 

#define GET_ALLOC(p) (GET(p) & 0x1)

- 사이즈 정보를 무시한 채 할당 여부를 나타내는 맨 뒷자리만 확인하는 함수

-  & 0x1 => ex) 1011 0111 & 0000 0001 = 0000 0001 = 1: Allocated 

 

#define HDRP(bp) ((char *)(bp) - WSIZE)

- bp가 속한 블록의 헤더를 알려주는 함수

- 블록 포인터(bp)를 char *로 캐스팅한 후 word size(4바이트)를 뺀다. 

- 블록 포인터는 페이로드 시작점을 가리키기 때문에 헤더의 크기인 4바이트만큼을 빼면 헤더를 가리키는 포인터가 될 것이다. 

 

#define FTRP(bp) ((char *)(bp) + GET_SIZE(HDRP(bp) - DSIZE))

- 블록 포인터(bp)에 해당 블록의 사이즈(header + footer + payload + padding)을 더하면 다음 블록의 페이로드를 가리키는 포인터가 된다. 따라서 8바이트(다음블록 헤더 + 현재 블록 푸터 를 빼서 푸터를 가리키는 포인터를 구한다. 

 

#define NEXT_BLKP(bp)  ((char *)(bp) + GET_SIZE((char *)(bp) - WSIZE))

- 다음 블록의 bp(페이로드의 주소) 

 

#define PREV_BLKP(bp)  ((char *)(bp) - GET_SIZE((char *)(bp) - DSIZE))

- 이전 블록의 bp

② mm_init

: mm_malloc, mm_free, mm_realloc을 실행하기 전 초기화해야하는 설정들을 넣는다.

함수 실행 도중 문제가 생긴다면 -1을  return, 정상적으로 종료되면 0을 return한다.

 

우리는 mm_init 함수를 통해 다음 그림과 같이 미사용 패딩, Prologue block의 header와 footer, Epilogue Block(only header)를 초기화를 해준다.

/* 
 * mm_init - initialize the malloc package.
 * 최초의 가용블록(4words)을 가지고 힙을 생성하고 할당기를 초기화한다. 
 */
int mm_init(void)
{   
    /* 메모리에서 4 word 가져오고 이걸로 빈 가용 리스트 초기화 */
    if ((heap_listp = mem_sbrk(4*WSIZE)) == (void *)-1)
        return -1;
    // mem_sbrk의 리턴 값은 항상 새로 늘어난 힙의 첫 번째 주소를 가리키고 있다.
    // 그렇기 때문에 지금 주석을 작성하는 시점에서의 heap_listp는 초기화된 가용 리스트의 첫 번째 주소를 가리킨다.
    // PUT 매크로: 주소 p가 가리키는 워드에 val을 저장하는 함수
    PUT(heap_listp, 0);                       /* Alignment padding: 더블 워드 경계로 정렬된 미사용 패딩 */
    PUT(heap_listp + (1*WSIZE), PACK(DSIZE, 1));    /* Prologue header */
    PUT(heap_listp + (2*WSIZE), PACK(DSIZE, 1));    /* Prologue footer */
    PUT(heap_listp + (3*WSIZE), PACK(0, 1));        /* Epilogue header */
    heap_listp += (2*WSIZE);    // 정적 전역 변수는 늘 prologue block을 가리킨다. 


    /*Extend the empty heap with a free block of CHUNKSIZE bytes*/
    // 그 후 CHUNKSIZE만큼 힙을 확장해 초기 가용 블록을 생성한다.
    
    // CHUNKSIZE는 바이트이기에 WSIZE로 나눠줌으로써 워드 단위로 만듬 
    // 즉, extend_heap은 워드 단위로 받음
    if (extend_heap(CHUNKSIZE / WSIZE) == NULL)
        return -1;
    return 0;
}

💡 미사용 패딩을 사용하는 이유

- prologue block 다음에 오는 실제 필요한 데이터를 더블 워드 정렬해주기 위해서

- 미사용 패딩을 사용해야 prologue block 뒤의 실제 데이터 블록들이 8의 배수로 정렬될 수 있다. 

③ extend_heap

static void *extend_heap(size_t words) // 워드 단위로 받는다.
{
    char *bp;       // 블록 포인터 선언
    size_t size;    // 힙 영역의 크기를 담을 변수 선언

    // 더블 워드 정렬에 따라 메모리를 mem_sbrk 함수를 이용해 할당받는다.
    // Double Word Alignment: 늘 짝수 개수의 워드를 할당해주어야 한다.
    size = (words % 2) ? (words + 1) * WSIZE : words * WSIZE; // words가 홀수라면 1을 더한 후 4바이트를 곱하고, 짝수라면 그대로 4바이트를 곱해서 size에 저장 (즉, size는 힙의 총 byte 수)
    if ((long)(bp = mem_sbrk(size)) == -1)                    // 새 메모리의 첫 부분을 bp로 둔다. 주소값은 int로는 못 받아서 long으로 casting
        return NULL;

    // 새 가용 블록의 header와 footer를 정해주고 epilogue block을 가용 블록 맨 끝으로 옮긴다.
    PUT(HDRP(bp), PACK(size, 0));         // free block header
    PUT(FTRP(bp), PACK(size, 0));         // free block footer
    PUT(HDRP(NEXT_BLKP(bp)), PACK(0, 1)); // new epliogue header: 항상 size 0, alloc 1

    // 만약 이전 블록이 가용 블록이라면 연결, 통합된 블록의 블록 포인터를 리턴
    return coalesce(bp);
}

④ mm_free

void mm_free(void *bp)
{
    // 해당 블록의 size를 알아내 header와 footer의 정보를 수정한다.
    size_t size = GET_SIZE(bp);
    PUT(HDRP(bp), PACK(size, 0));
    PUT(FTRP(bp), PACK(size, 0));

    // 만약 앞뒤의 블록이 가용 상태라면 연결한다.
    coalesce(bp);
}

⑤ coalesce

// 해당 가용 블록을 앞 뒤 가용 블록과 연결하고 가용 블록의 주소를 리턴한다.
static void *coalesce(void *bp){   
    // bp: free 상태의 블록의 payload를 가리키고 있는 포인터 

    size_t prev_alloc = GET_ALLOC(FTRP(PREV_BLKP(bp))); // 직전 블록의 헤더에서 가용 여부
    size_t next_alloc = GET_ALLOC(HDRP(NEXT_BLKP(bp))); // 직후 블록의 푸터에서 가용 여부
    size_t size = GET_SIZE(HDRP(bp));

    // case 1: 직전, 직후 블록이 모두 할당
    // 연결 불가, 그대로 bp 리턴 
    if (prev_alloc && next_alloc)
        return bp;

    // case 2: 직전 블록 할당, 직후 블록 가용
    else if (prev_alloc && !next_alloc)
    {
        size += GET_SIZE(HDRP(NEXT_BLKP(bp)));      // 직후 블록 사이즈를 현재 블록 사이즈와 합체
        PUT(HDRP(bp), PACK(size, 0));               // 현재 블록 헤더값 갱신
        PUT(FTRP(bp), PACK(size, 0));               // 현재 블록 푸터값 갱신
                                                    // 블록 포인터는 변경할 필요 없다.
    }

    // case 3: 직전 블록 가용, 직후 블록 할당
    else if (!prev_alloc && next_alloc)
    {
        size += GET_SIZE(HDRP(PREV_BLKP(bp)));      // 직전 블록 사이즈를 현재 블록 사이즈와 합체
        PUT(HDRP(PREV_BLKP(bp)), PACK(size, 0));    // 직전 블록 헤더값 갱신
        PUT(FTRP(bp), PACK(size, 0));               // 현재 블록 푸터값 갱신
        bp = PREV_BLKP(bp);                         // 블록 포인터를 직전 블록으로 옮긴다.
    }

    // case 4: 직전, 직후 블록 모두 가용
    else
    {
        size += GET_SIZE(HDRP(PREV_BLKP(bp))) + GET_SIZE(FTRP(NEXT_BLKP(bp)));
        PUT(HDRP(PREV_BLKP(bp)), PACK(size, 0));    // 직전 블록 헤더값 갱신
        PUT(FTRP(NEXT_BLKP(bp)), PACK(size, 0));    // 직후 블록 푸터값 갱신
        bp = PREV_BLKP(bp);                         // 블록 포인터를 직전 블록으로 옮긴다.
    }

    // 최종 가용 블록의 주소를 리턴한다.
    return bp;
}

⑥ mm_malloc

void *mm_malloc(size_t size)
{
    size_t asize;           // 정렬 조건과 헤더 & 푸터 용량을 고려하여 조정된 블록 사이즈
    size_t extendsize;      // 메모리를 할당할 자리가 없을 때 (no fit) 힙을 연장할 크기
    char *bp;

    // 가짜 요청 spurious request 무시
    if (size == 0)
        return NULL;

    if (size <= DSIZE)      // 정렬 조건 및 오버헤드(= 헤더 & 푸터 크기)를 고려하여 블록 사이즈 조정
        asize = 2 * DSIZE;  // 요청받은 크기가 8바이트보다 작으면 aszie를 16바이트로 만든다. 
    else
        asize = DSIZE * ((size + (DSIZE) + (DSIZE-1)) / DSIZE);
        // 요청받은 크기가 8바이트 보다 크다면, 사이에 8바이트를 더하고 (오버헤드) 다시 7을 더해서(올림 효과를 주기 위함) 8로 나눈 몫에 8을 곲한다. 

    // 가용 리스트에서 적합한 자리를 찾는다.
    if ((bp = find_fit(asize)) != NULL)
    {                       
        place(bp, asize);   
        return bp;
    }

    // 만약 맞는 크기의 가용 블록이 없다면 새로 힙을 늘려서
    extendsize = MAX(asize, CHUNKSIZE); // 둘 중 더 큰 값으로 사이즈를 정한다.
    // extend_heap()은 word 단위로 인자를 받으므로 WSIZE로 나눠준다.
    if ((bp = extend_heap(extendsize / WSIZE)) == NULL)
        return NULL;
    // 새 힙에 메모리를 할당한다.
    place(bp, asize);
    return bp;
}

⑦ find_fit - Next fit 방법

static void *find_fit(size_t asize)
{
/* Next fit 방법 */
    void *bp = last_bp;
    for (bp = NEXT_BLKP(bp) ; GET_SIZE(HDRP(bp))>0 ; bp = NEXT_BLKP(bp))
    {
        if (GET_ALLOC(HDRP(bp)) == 0 && asize <= GET_SIZE(HDRP(bp))) 
        {
            last_bp =bp;
            return bp;
        }
    }
    bp = heap_listp;
    while (bp < last_bp) {
        bp = NEXT_BLKP(bp);
        if (!GET_ALLOC(HDRP(bp)) && asize <= GET_SIZE(HDRP(bp))) {
            last_bp = bp;
            return bp;
        }
    }
    return NULL;
}

⑧ place

static void place(void *bp, size_t asize){
    // 현재 할당할 수 있는 후보 가용 블록의 주소
    size_t csize = GET_SIZE(HDRP(bp));

    // 분할이 가능한 경우
    // => 남은 메모리가 최소한의 가용 블록을 만들 수 있는 4word(16byte)가 되느냐
    // => why? 적어도 16바이트 이상이어야 이용할 가능성이 있음 
    // header & footer: 1word씩, payload: 1word, 정렬 위한 padding: 1word = 4words
    if ((csize - asize) >= (2 * DSIZE))
    {
        // 앞의 블록은 할당 블록으로
        PUT(HDRP(bp), PACK(asize, 1));          // 헤더값 갱신
        PUT(FTRP(bp), PACK(asize, 1));          // 푸터값 갱신
        // 뒤의 블록은 가용 블록으로 분할한다.
        bp = NEXT_BLKP(bp);                     // 다음블록 위치로 bp 이동
        PUT(HDRP(bp), PACK(csize - asize, 0));  // 남은 가용 블록의 헤더 갱신
        PUT(FTRP(bp), PACK(csize - asize, 0));  // 남은 가용 블록의 푸터 갱신
    }
    // 분할할 수 없다면 남은 부분은 padding한다.
    else
    {
        PUT(HDRP(bp), PACK(csize, 1));
        PUT(FTRP(bp), PACK(csize, 1));
    }
}

 

Reference

Computer Systems: A Programmer's Perspective, Global Edition (Paperback, 3 ed)

메모리 정적 할당 VS 동적 할당(Stack VS Heap): https://suyeon96.tistory.com/26

Malloc-lab 정리에 도움된 글: https://velog.io/@cjy13753/malloc-lab-%EC%A0%95%EB%A6%AC