Malloc Lab은 C언어를 기반으로 한 교육용 프로젝트입니다.
Malloc Lab을 통해서 동적 메모리 할당의 개념과 구현을 학습할 수 있습니다.

프로젝트를 진행하기 전에, 과제 설명서를 읽어보고, 이해해봅니다.
다음의 과제 설명서에서 불필요한 내용은 제외했습니다.

Malloc Lab 과제 설명서

1. 서론

이 과제에서는 C 프로그램을 위한 동적 메모리 할당자를 작성한다.
즉, malloc, free, realloc를 직접 구현한다.
정확하고 효율적이며 빠른 할당자를 구현하는 것을 목표로 한다.

2. 배포

파일들 중 mm.c만 수정하여 제출한다.
mdriver.c 프로그램은 채점을 돕는 프로그램이다.
make 명령어로 컴파일하고, ./mdriver -v 명령어로 실행하면 성능을 측정할 수 있다.
(-V는 유용한 요약 정보를 표시한다.)

3. 과제 수행 방법

동적 메모리 할당자에서 다음 네 개의 함수를 구현한다.
이 함수들은 mm.h에 선언되어 있고, mm.c에 정의되어 있다.

int mm_init(void);
void *mm_malloc(size_t size);
void mm_free(void *ptr);
void *mm_realloc(void *ptr, size_t size);

제공된 mm.c 파일은 기능적으로 올바르지만, 아주 단순한 malloc 패키지이다.
이를 기반으로 함수를 수정하고, 필요하다면 정적(static) 함수를 추가적으로 정의한다.
이 함수들은 다음과 같은 역할을 한다.

1) mm_init

mm_malloc, mm_realloc, mm_free가 호출되기 전, 채점 프로그램이 호출하여 필요한 초기화를 수행하는 함수이다.
초기 힙 영역 할당과 같은 작업을 수행할 수 있다.
초기화에 실패하면 -1을 반환하고, 성공하면 0을 반환한다.

2) mm_malloc

요청한 size 바이트의 block payload에 대한 포인터를 반환하는 함수이다.

block: 메모리에서 하나의 단위. 보통은 payload + 관리 정보(header/footer)를 포함한다.
payload: 사용자가 실제로 사용하게 되는 공간

할당된 메모리는 프로그램의 힙 영역 안에 있어야 하고, 다른 할당된 chunk와 겹치지 않아야 한다.

chunk: block과 같은 뜻으로 많이 사용된다. 표준 C 라이브러리에서 주로 이 표현을 사용한다.

구현된 코드는 표준 C 라이브러리(libc)의 malloc 버전과 비교된다.
libc malloc은 항상 8바이트에 정렬(8-byte aligned)된 payload 포인터를 반환하기 때문에, malloc 구현시 8바이트 정렬된 포인터를 반환해야 한다.

3) mm_free

포인터가 가리키는 블록을 해제하는 함수이며, 반환값은 없다.
이 함수는 포인터가 이전에 mm_malloc 또는 mm_realloc으로 반환된 것이며, 아직 free되지 않은 경우에만 안전하게 사용할 수 있다

4) mm_realloc

요청한 size만큼 메모리를 다시 할당하고, 그 시작 포인터를 반환하는 함수이다.

• ptr이 NULL이면, 호출은 mm_malloc(size)와 동일하다. (즉, 새로운 메모리 요청)
• size가 0이면, 호출은 mm_free(ptr)과 동일하다. (즉, 메모리 해제)
• ptr이 NULL이 아닌 경우, 이는 이전에 mm_malloc 또는 mm_realloc 호출에 의해 반환된 것이어야 한다.

mm_realloc 호출은 포인터가 가리키는 메모리 블록의 크기를 기존 size 바이트로 변경하고, 새 블록의 주소를 반환한다.
새 블록의 주소는 구현 방식, 기존 블록의 내부 단편화, 요청된 크기에 따라 이전과 같거나 다를 수 있다.

새 블록의 내용은 이전 블록의 데이터와 동일하지만, 그 범위는 old size와 new size 중 더 작은 쪽까지만 보장된다.

예로, 이전 블록이 8바이트이고 새 블록이 12바이트이면, 새 블록의 처음 8바이트는 이전과 동일하며 나머지 4바이트는 초기화되지 않는다.
반대로 이전 블록이 8바이트이고 새 블록이 4바이트이면, 새 블록은 앞의 4바이트만 복사되고, 나머지는 버려진다.

이 동작은 libc의 malloc, realloc, free 함수의 의미와 일치한다.

4. 힙 일관성 검사기(Heap Consistency Checker)

(1) 작성해야 하는 이유

동적 메모리 할당자는 정확하고 효율적으로 작성하기 까다롭다.
대부분 형(type)이 없는 포인터 연산으로 이루어져 있기 때문에, 오류가 발생하기 쉽고 디버깅도 어렵기 때문이다.
따라서 직접 구현한 할당자의 힙 구조를 검사하는 일관성 검사기(heap checker)를 직접 작성해보는 것이 도움이 될 것이다.

(2) 체크할 수 있는 예시들

• free 리스트에 있는 모든 블록이 실제로 free 상태로 표시되어 있는가?
• 연속된 free 블록이 병합되지 않고 남아있지는 않은가?
• 모든 free 블록이 실제로 free 리스트에 포함되어 있는가?
• free 리스트 안의 포인터들이 실제로 유효한 free 블록을 가리키고 있는가?
• 할당된 블록들 사이에 겹침(overlap)이 존재하는가?
• 힙 안의 포인터들이 유효한 힙 주소 범위를 가리키고 있는가?

(3) 구현 방식

힙 검사기는 mm.c 파일 내에서 int mm_check(void) 함수로 구현되어야 한다.
이 함수는 적절하다고 판단되는 불변 조건(invariant) 또는 일관성 조건(consistency condition)들을 검사한다.

• 힙이 일관된 상태일 경우 → 0이 아닌 값을 반환
• 일관성에 문제가 있으면 → 0 또는 오류 메시지 출력

제시된 항목들을 전부 검사할 필요는 없으며, 이 외 필요하다고 판단된다면 자유롭게 검사 항목을 추가할 수 있다.

(4) 사용 시 주의사항

이 일관성 검사기는 개발 도중, 디버깅 용도로만 사용하는 것이다.
과제를 제출하기 전에, mm.c 안에서 이 함수를 호출하는 부분은 반드시 제거해야 한다.
검사 기능이 남아 있으면 처리 속도 (throughput)가 떨어질 수 있기 때문이다.

(5) 스타일 점수 관련

mm_check() 함수는 스타일 점수 10점 중 일부(5점)에 해당된다.
따라서 검사하는 항목들에 주석을 잘 달고, 어떤 불변 조건을 확인하는지를 명확히 문서화해야 한다.

5. 지원 함수들

memlib.c 패키지는 동적 메모리 할당자를 위한 메모리 시스템을 시뮬레이션하는 역할을 한다.
memlib.c 안에는 다음과 같은 함수들이 제공된다.

1) void *mem_sbrk(int incr)

힙을 incr 바이트만큼 확장한다.
incr는 반드시 0보다 큰 양의 정수여야 한다.
이 함수는 새로 확장된 힙 영역의 첫 번째 바이트를 가리키는 포인터를 반환한다.
Unix 시스템에서의 sbrk 함수와 동일한 의미를 가지지만, mem_sbrk는 오직 양의 정수만 인자로 받을 수 있다는 것이 차이점이다.

2) void *mem_heap_lo(void)

힙의 시작 주소(가장 낮은 주소)를 가리키는 포인터를 반환한다.

3) void *mem_heap_hi(void)

힙의 끝 주소(가장 높은 주소)를 가리키는 포인터를 반환한다.

4) size_t mem_heapsize(void)

현재 힙의 전체 크기를 바이트 단위로 반환한다.

5) size_t mem_pagesize(void)

시스템의 페이지 크기(바이트 단위)를 반환한다.
일반적으로 리눅스에서는 4KB(=4096Byte)이다.

6. 트레이스 기반 드라이버 프로그램

malloclab-handout.tar에 포함된 드라이버 프로그램 mdriver.c는 다음과 같은 항목들을 평가한다.

• mm.c 구현이 올바르게 작동하는지(정확성),
• 얼마나 메모리를 효율적으로 사용하는지(공간 활용도),
• 얼마나 빠른지(처리량, throughput)

mdriver.c는 malloclab-handout.tar에 함께 들어 있는 여러 개의 트레이스 파일(trace file)을 이용하여 동작한다.

각 트레이스 파일에는 할당(allocate), 재할당(reallocate), 해제(free) 등의 작업이 순서대로 기록되어 있다.
드라이버는 이 지시사항들을 읽고, 구현한 mm_malloc, mm_realloc, mm_free 함수를 그 순서대로 호출한다.

이 드라이버 프로그램과 트레이스 파일은 mm.c 파일을 채점할 때도 동일하게 사용된다.

💡 드라이버 mdriver.c가 사용하는 명령줄 옵션

• -t <tracedir>
  기본 설정된 디렉터리 대신, <tracedir> 디렉터리에서 트레이스 파일을 찾도록 한다.

• -f <tracefile>
  여러 트레이스 중 하나가 아니라, 특정 트레이스 파일 하나만을 사용하여 테스트한다.

• -h
  명령줄 옵션들의 요약된 설명을 출력한다.

• -l
  malloc 구현뿐만 아니라, 표준 라이브러리(libc)의 malloc도 함께 실행 및 측정한다.

• -v
  자세한 출력: 각 트레이스 파일에 대한 성능을 간결한 표 형식으로 요약해서 보여준다.

• -V
  더 자세한 출력: 각 트레이스 파일이 처리되는 동안 추가적인 진단 정보를 출력한다.
  → malloc 구현이 어떤 트레이스에서 실패하는지를 디버깅할 때 매우 유용하다.

7. 프로그래밍 규칙

과제를 수행할 때 아래 규칙들을 반드시 지켜야 한다.
규칙들을 위반하면 점수가 0점이 될 수도 있으니 주의하라.

1) 함수 인터페이스 변경 금지

mm.c 안에 있는 함수들의 인터페이스(함수 선언 부분)를 변경해서는 안된다.
즉, 함수 이름, 인자, 반환값 등을 바꾸면 안된다.

2) 라이브러리 사용 금지

어떤 종류든, 메모리 관련 라이브러리 함수나 시스템 호출을 사용해서는 안된다.
→ 특히 다음 함수들은 절대 사용하면 안된다:

• malloc
• calloc
• free
• realloc
• sbrk
• brk

이들의 변형 함수들도 포함된다.

3) 전역/정적 복합 자료구조 선언 금지

mm.c 안에서 다음과 같은 전역 또는 정적 복합 자료구조(compound data structures)를 선언할 수 없다.

• 배열(array)
• 구조체(struct)
• 트리(tree)
• 리스트(list)

즉, 전역 영역에 이런 자료구조를 선언하면 안된다.

단, 아래와 같은 기본형 스칼라 변수(scalar variables)는 전역 또는 정적으로 선언할 수 있다.

• 정수형 변수 (int)
• 실수형 변수 (float)
• 포인터 (void, char 등)

표준 라이브러리의 malloc과 일관성을 유지하기 위해, 구현한 메모리 할당자도 항상 8바이트 정렬된 포인터(주소)를 반환해야 한다.
(예: 반환된 주소가 0x100, 0x108, 0x110처럼 8의 배수여야 한다)
이 조건은 드라이버 프로그램이 자동으로 검사한다.

8. 평가

규칙을 위반하거나, 코드의 버그로 인해 드라이버 프로그램이 crash된다면, 0점을 부여한다.
그 외에 점수는 아래와 같이 산정된다.

1) 정확성 (20점)

드라이버 프로그램이 수행하는 정확성 테스트를 모두 통과하면 만점이다.
각 트레이스 파일을 올바르게 처리하면 부분 점수가 주어진다.

2) 성능 (35점)

성능 평가는 다음 두 가지 기준을 사용해 이루어진다.

1. 메모리 활용률
   드라이버가 사용하는 전체 메모리(즉, mm_malloc 또는 mm_realloc으로 할당되었지만 아직 mm_free되지 않은 메모리)의 합계와 할당자가 사용한 힙 크기 간의 비율이다.
   이 비율이 1에 가까울수록 메모리를 낭비 없이 잘 썼다는 뜻이다.
   단편화(fragmentation)를 줄이는 전략을 통해 이 비율을 최대한 1에 가깝게 만들어야 한다.

2. 처리량
   초당 몇 개의 연산을 처리했는지를 나타내는 평균 연산 속도이다.

💡 성능 요약 지표

드라이버 프로그램은 아래와 같은 성능 지수 P를 계산하여 할당자 성능을 요약한다.

P = wU + (1 − w) * min(1, T / Tlibc)

• U: 메모리 활용률
• T: 처리량
• Tlibc: 기본 트레이스에서의 libc malloc의 기준 처리량
  (이 값은 드라이버 프로그램 안에서 미리 정해져 있으며, 보통 600 Kops/s이다)
• w: 가중치 (기본값은 0.6이다)

즉, 공간 효율을 더 중요하게 생각하되, 처리량도 반영하는 방식이다.

💡 위 공식을 사용하는 이유

메모리와 CPU는 모두 중요한 자원이기 때문에, 메모리 활용률과 처리량을 균형 있게 최적화하도록 유도하고자 이 공식을 사용한다.
이상적으로는 성능 지수 P가 다음과 같이 최대값 1(100%)에 도달하는 것이 목표이다.

P = w + (1 - w) = 1

각 성능 항목은 P에 최대 w, 1-w만큼 영향을 주므로, 어느 한쪽만 극단적으로 최적화하는 것은 바람직하지 않다.
좋은 점수를 받기 위해서는 메모리 활용률과 처리 속도 사이에서 균형을 잡아야 한다.

3) 스타일 (10점)

다음 항목을 기준으로 스타일 점수가 부여된다.

• 코드가 함수 단위로 잘 분리되어 있고, 전역 변수는 가능한 한 적게 사용해야 한다.
• 코드의 맨 위에는 다음 내용이 포함된 설명 주석이 있어야 한다.
  • free 블록과 할당 블록의 구조 설명
  • free 리스트의 구성 방식
  • 할당자가 free 리스트를 어떻게 조작하는지
• 각 함수 앞에는 무엇을 하는 함수인지 설명하는 주석이 있어야 한다.
• Tlibc 값(기준 처리량)은 드라이버에 상수로 정의되어 있으며, 출제자가 과제 환경 설정 시 600 Kops/s로 정한 값이다.
• 힙 일관성 검사 함수 mm_check()는 문서화가 잘 되어있어야 하며, 아래 항목 각각에 5점씩 부여된다.
  • 훌륭한 힙 검사기 작성
  • 구조화된 코드와 충분한 설명 주석

9. 힌트

(1) mdriver -f 옵션 사용하기

초기 개발 단계에서, 아주 작은 트레이스 파일을 사용하는 것은 디버깅과 테스트를 훨씬 쉽게 만들어준다.
short1.rep, short2-bal.rep 같은 간단한 트레이스 파일 2개가 제공되어 있다.
이 파일들을 초기 디버깅에 활용한다.

트레이스 파일(trace file): 미리 정해진 malloc, free, realloc의 호출 순서를 담고 있는 텍스트 파일이다.

(2) mdriver -v 와 -V 옵션 사용하기

-v 옵션은 각 트레이스 파일에 대한 성능 요약을 상세하게 보여준다.
-V 옵션은 어떤 트레이스 파일이 실행되고 있는지를 표시해주기 때문에, 어떤 트레이스에서 오류가 발생하는지 빠르게 확인할 수 있다.

(3) gcc -g로 컴파일하고 디버거 사용하기

디버거는 배열 범위를 벗어난 접근이나 잘못된 포인터 사용 등 메모리와 관련되니 오류를 찾는 데 큰 도움이 된다.

(4) 교과서의 malloc 구현 예제를 완벽하게 이해하기

교재에는 implicit free list 기반의 간단한 메모리 할당자 예제가 자세히 설명되어 있다.
이 예제를 출발점으로 삼는 것이 좋다.
이 간단한 구현을 완전히 이해하지 못했다면, 할당자 구현을 시작하지 마라.

(5) 포인터 연산을 C 전처리기 매크로로 캡슐화하기

메모리 관리 코드는 포인터 연산이 많고, 이 과정에서 형 변환(casting)이 자주 필요하기 때문에 매우 헷갈리고 오류가 나기 쉽다.
포인터 연산을 매크로로 작성하면 복잡함을 크게 줄일 수 있다.
교재에 좋은 예시들이 나와있다.

(6) 구현을 단계별로 수행하기

처음 9개의 트레이스는 malloc과 free 요청만 포함되어 있고, 마지막 2개의 트레이스는 realloc, malloc, free 요청을 모두 포함하고 있다.
따라서 먼저 malloc과 free가 정확하게 동작하고 효율적으로 작성하도록 만드는 데 집중해라.
이 부분이 잘 동작하면 그 다음에 readloc 구현에 집중하면 된다.
처음에는 기존 malloc과 free를 활용해서 realloc을 만들 수 있다.
하지만 좋은 성능을 내기 위해서는 realloc을 독립적으로 구현해야 한다.

(7) 프로파일러 사용하기

성능 최적화를 위해 gprof 같은 도구가 도움이 될 수 있다.