Implicit Free List 기반 동적 할당기 구현하기
들어가며
malloc_lab은 CSAPP에서 제공하는 실습으로, malloc, free, realloc 같은 동적 메모리 할당 기능을 직접 구현해보는 실습 과제입니다. 가장 기본적으로 달성해야 할 첫 번째 목표는 implicit free list 기반으로 간단한 동적 할당기를 구현하는 것입니다.
기본적으로 제공되는 코드는 CSAPP 교재에서 제시한 implicit free list 방식을 사용하지만, 모든 코드가 다 주어지는 것은 아닌데요. malloc, free와 같은 핵심적인 기능 중 일부는 코드를 제공하지 않고, 학생들이 직접 구현하도록 의도적으로 비워놓은 부분이 있습니다. 다만, 이런 부분에 대해서는 9장 끝부분에 해답 코드를 제공하고 있죠.
realloc 함수는 특히 아예 코드가 주어지지 않으며, malloc_lab 초기 버전에서는 성능 최적화 없이 동작하는 임시 realloc을 제공하는데요. 이를 통해 malloc과 free의 동작 여부만 간단히 테스트할 수 있게 되어 있습니다.
구현해야 할 주요 함수는 크게 두 그룹으로 나뉩니다.
- 핵심 기능 함수:
mm_init: 동적 할당기를 초기화하는 함수mm_malloc: 실제 메모리 할당을 수행하는 함수mm_free: 할당된 메모리를 해제하는 함수mm_realloc: 메모리 재할당을 수행하는 함수
- 보조(파츠) 함수:
extend_heap: 힙 영역을 확장할 때 사용하는 함수coalesce: 인접한 free 블록을 병합하는 함수find_fit: 요청한 크기에 맞는 블록을 찾는 함수place: 찾은 블록에 실제로 할당을 수행하는 함수
implicit free list 방식은 간단한 방식이어서 구현 자체는 어렵지 않지만, 성능 최적화를 위해 이후 explicit free list나 segregated list 방식으로의 발전이 필요할 수 있습니다.
기본 매크로 및 전역 변수 소개
malloc, free, realloc을 구현하기 위해서는, 블록의 크기나 상태를 다루는 기본 연산들이 필요한데요. 이를 매번 함수로 만들기엔 비효율적이기 때문에, 코드에서는 간결하고 빠른 처리를 위해 매크로를 적극적으로 사용합니다. 아래는 앞으로 동적 메모리 할당기의 구현에서 계속해서 사용하게 될 핵심 매크로와 전역 변수 목록입니다.
기본 상수 (64비트 기준)
먼저 기본 코드에 주어져 있는 ALIGNMENT(정렬 기준)은 32비트 기준인 8로 설정되어 있으므로 이를 16으로 바꿔줍니다. 그리고 GET, PUT 매크로에서 기존 4바이트 기반 주소인 unsigned int형으로 되어 있는 것을 8바이트 기반 주소인 unsigned long 형으로 바꿔줍니다.
// 수정해야 할 기존 매크로
#define ALIGNMENT 16 // 정렬 기준 (16바이트)
#define ALIGN(size) (((size) + (ALIGNMENT - 1)) & ~0xF) // 정렬 기준에 맞춰 0x7 -> 0xF로 변경
#define GET(p) (*(unsigned long *)(p)) // 인자 p가 참조하는 워드를 읽어서 리턴
#define PUT(p, val) (*(unsigned long *)(p) = (val)) // 인자 p가 가리키는 워드에 val 저장
// 신규 매크로
#define WSIZE 8 // 워드 크기 (4바이트)
#define DSIZE 16 // 더블 워드 크기 (8바이트)
#define CHUNKSIZE (1 << 12) // 초기 확장 크기 (4KB)- WSIZE: 헤더나 푸터에 저장되는 기본 단위 크기
- DSIZE는 더블 워드 크기. 힙 정렬(Alignment)을 위해 최소 블록 크기 단위로 사용
- CHUNKSIZE: 힙을 한 번에 얼마만큼 확장할지를 나타냄 (보통 4KB 단위)
기본 연산 매크로
#define MAX(x, y) ((x) > (y) ? (x) : (y))
#define PACK(size, alloc) ((size) | (alloc))- MAX(x, y): 둘 중 더 큰 값을 반환
- PACK(size, alloc): 크기(size)와 할당 여부(alloc)를 하나의 값으로 묶음
메모리 읽기/쓰기 매크로
#define GET(p) (*(unsigned int *)(p))
#define PUT(p, val) (*(unsigned int *)(p) = (val))- GET(p): 포인터 p가 가리키는 위치의 값을 읽어옴
- PUT(p, val): 포인터 p가 가리키는 위치에 val을 저장
헤더, 푸터, 블록 간 이동 매크로
#define GET_SIZE(p) (GET(p) & ~0x7)
#define GET_ALLOC(p) (GET(p) & 0x1)
#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)))- GET_SIZE(p): 헤더/푸터에서 블록 크기 추출
- GET_ALLOC(p): 헤더/푸터에서 할당 여부 추출
- HDRP(bp): bp 포인터 기준으로 해당 블록의 헤더 위치를 반환
- FTRP(bp): bp 포인터 기준으로 해당 블록의 푸터 위치를 반환
- NEXT_BLKP(bp): bp 다음 블록의 포인터를 반환
- PREV_BLKP(bp): bp 이전 블록의 포인터를 반환
전역 변수
static char *heap_listp;- heap_listp는 항상 현재 힙 영역의 시작을 가리킨다.
- 특히 프롤로그 블록의 중앙(헤더와 푸터 사이)을 가리키는 것이 일반적이다.
동적 할당기 초기화 (mm_init)
mm_init 함수는 동적 메모리 할당기에서 초기 힙(Heap) 구조를 세팅하는 함수인데요. 할당기의 malloc과 free가 제대로 동작하기 위해 필요한 기본 틀을 만들어주는 역할을 합니다.
구체적으로는 다음과 같은 작업을 진행하게 됩니다.
- 힙에 Prologue Block(초기화 블록)과 Epilogue Header(힙의 끝 표시)를 세팅한다.
- 첫 번째 Free Block을 만들기 위해 힙을 일정 크기(CHUNKSIZE)만큼 확장한다.
한마디로, malloc, free가 동작할 수 있도록 힙을 초기 설정하는 준비 단계라고 생각하면 됩니다.
mm_init 구현하기
int mm_init(void)
{
// 총 4 워드 크기만큼 힙 영역을 요청
// - PADDING
// - PROLOGUE_HEADER
// - PROLOGUE_FOOTER
// - EPILOGUE_HEADER
if ((heap_listp = mem_sbrk(4 * WSIZE)) == (void *)-1) {
// 메모리 확장 실패 시 에러 리턴
return -1;
}
// Padding: 16바이트 정렬을 위한 더미 워드
PUT(heap_listp, 0);
// Prologue Header: 크기 8바이트, 할당된 상태 1
PUT(heap_listp + (1 * WSIZE), PACK(DSIZE, 1));
// Prologue Footer: 크기 8바이트, 할당된 상태 1
PUT(heap_listp + (2 * WSIZE), PACK(DSIZE, 1));
// Epilogue Header: 크기 0, 할당된 상태 1 → 힙 끝을 표시
PUT(heap_listp + (3 * WSIZE), PACK(0, 1));
// heap_listp를 Prologue Footer 바로 다음으로 이동
heap_listp += (2 * WSIZE);
// Free Block을 만들기 위해 힙을 CHUNKSIZE만큼 확장
if (extend_heap(CHUNKSIZE / WSIZE) == NULL) {
// 확장 실패 시 에러 리턴
return -1;
}
// 초기화 성공
return 0;
}
힙 확장 함수 (extend_heap)
extend_heap 함수는 힙 영역을 추가로 확장하는 함수입니다. 이미 위의 mm_init에서 해당 함수가 호출되는 것을 보셨을 것 같은데요. 초기 힙 생성 시 뿐만 아니라, malloc 요청을 처리할 때 빈 공간이 부족하면 이 함수를 통해 새로운 메모리 영역을 확보하게 됩니다.
구체적으로는 다음과 같은 작업을 진행하게 됩니다.
- 요청받은 크기만큼 힙을 늘린다.
- 새로 확장된 공간을 하나의 Free Block으로 만든다.
- 확장된 Free Block과 기존 Free Block을 병합(coalesce)할 수 있도록 준비한다.
정리하자면, 메모리 공간이 부족할 때 힙을 늘려서 새 Free Block을 만드는 함수라고 보면 됩니다.
extend_heap 구현하기
static void *extend_heap(size_t words) {
char *bp;
size_t size;
// 짝수 워드 수만큼 크기를 조정 (Alignment 유지)
if (words % 2) {
size = (words + 1) * WSIZE; // 홀수면 +1 해서 짝수로 맞추기
} else {
size = words * WSIZE;
}
// 힙을 size 바이트 만큼 확장
if ((long)(bp = mem_sbrk(size)) == -1) {
// mem_sbrk 실패 시 NULL 반환
return NULL;
}
// 새로 확장된 공간을 Free Block으로 초기화
PUT(HDRP(bp), PACK(size, 0)); // 새 Free Block의 헤더
PUT(FTRP(bp), PACK(size, 0)); // 새 Free Block의 푸터
// 마지막에 새 에필로그 헤더 설정
PUT(HDRP(NEXT_BLKP(bp)), PACK(0, 1)); // 크기 0, 할당된 상태 1
// 만약 앞쪽 블록도 Free였다면 병합(coalesce)
return coalesce(bp);
}
인접 블록 병합 함수 (coalesce)
coalesce 함수는 Free Block(해제된 블록)끼리 인접해 있을 때, 하나로 합쳐주는 함수입니다. 메모리를 해제하거나 힙을 확장할 때 호출되며, 메모리 단편화(Fragmentation) 를 줄이는 데 매우 중요한 역할을 하죠.
구체적으로는 다음과 같은 작업을 진행하게 됩니다.
- 이전 블록이 Free인지, 다음 블록이 Free인지 확인한다.
- 상황에 따라 현재 블록을 이전/다음 블록과 합친다.
- 필요하다면 양쪽 모두 합쳐서 하나의 큰 Free Block으로 만든다.
즉, Free Block 옆에 또 Free Block이 있는 경우 하나로 합쳐 더 큰 빈 공간을 만드는 함수입니다.
coalesce 구현하기
static void *coalesce(void *bp) {
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: 이전과 다음 블록이 모두 할당된 상태 (병합 X)
if (prev_alloc && next_alloc) {
return bp;
}
// Case 2: 이전 블록이 할당되어 있고, 다음 블록은 Free인 상태
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: 이전 블록이 Free이고, 다음 블록은 할당된 상태
else if (!prev_alloc && next_alloc) {
size += GET_SIZE(HDRP(PREV_BLKP(bp))); // 이전 블록 크기를 합친다
PUT(FTRP(bp), PACK(size, 0)); // 새 푸터 설정
PUT(HDRP(PREV_BLKP(bp)), PACK(size, 0)); // 이전 블록 헤더를 갱신
bp = PREV_BLKP(bp); // 포인터를 병합된 블록의 시작으로 이동
}
// Case 4: 이전과 다음 블록이 모두 Free인 상태
else {
size += GET_SIZE(HDRP(PREV_BLKP(bp))) + GET_SIZE(HDRP(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; // 병합 후의 블록 포인터 반환
}
블록 탐색(find_fit)과 배치(place)
find_fit 함수 소개
find_fit 함수는 Free Block들 중에서 요청한 크기만큼 담을 수 있는 블록을 찾는 함수인데요. 할당 요청(malloc)이 들어왔을 때 가장 먼저 필요한 작업이 바로 이 '빈 블록 찾기'입니다.
구체적으로는 다음과 같은 작업을 진행하게 됩니다.
- 힙을 처음부터 순차적으로 스캔하면서, (first-fit)
- 아직 할당되지 않은 블록 중 크기가 충분한 블록을 찾아낸다.
한마디로, 요청 크기에 맞는 빈 블록을 힙에서 찾아오는 함수입니다.
find_fit 구현하기
static void *find_fit(size_t asize) {
char *bp = heap_listp + 8; // 프롤로그 블록 페이로드 시작 위치
while ((GET_SIZE(HDRP(bp)) | !GET_ALLOC(HDRP(bp))) != 0) {
size_t bp_size = GET_SIZE(HDRP(bp)); // 현재 블록 크기
int alloc = GET_ALLOC(HDRP(bp)); // 현재 블록 할당 여부
// 현재 블록이 Free이고, 요청한 크기보다 크거나 같으면
if (alloc == 0 && bp_size >= asize) {
return bp; // 이 블록 사용
}
// 아니면 다음 블록으로 이동
bp += bp_size;
}
// 적당한 블록을 찾지 못하면 NULL 반환
return NULL;
}
place 함수 소개
place 함수는 find_fit으로 찾은 Free Block에 실제로 메모리를 할당하는 함수입니다. 요청한 크기만큼 할당한 후, 남는 공간이 있다면 새로운 Free Block으로 잘라서 다시 관리합니다.
구체적으로는 다음과 같은 작업을 진행하게 됩니다.
- 요청한 크기만큼 블록을 배치하고,
- 남은 공간이 충분히 크면 Split(쪼개기)해서 새로운 Free Block을 만든다.
곧, 찾은 빈 블록을 적절히 잘라 메모리 할당을 해주는 함수라고 할 수 있습니다.
place 구현하기
static void place(void *bp, size_t asize) {
size_t csize = GET_SIZE(HDRP(bp)); // 현재 블록의 전체 크기
// 남은 공간이 최소 블록 크기(32바이트)보다 크면 Split
if (csize - asize >= 2 * DSIZE) {
// 요청한 크기로 할당
PUT(HDRP(bp), PACK(asize, 1));
PUT(FTRP(bp), PACK(asize, 1));
// 나머지 공간은 새로운 Free Block으로 설정
bp = NEXT_BLKP(bp);
PUT(HDRP(bp), PACK(csize - asize, 0));
PUT(FTRP(bp), PACK(csize - asize, 0));
}
// 남은 공간이 너무 작으면 그냥 모두 할당
else {
PUT(HDRP(bp), PACK(csize, 1));
PUT(FTRP(bp), PACK(csize, 1));
}
}
메모리 할당 함수 (mm_malloc)
mm_malloc 함수는 사용자가 요청한 크기의 메모리를 힙에서 할당하는 함수인데요. 지금까지 만든 find_fit, place, extend_heap 같은 보조 함수들을 조합해서 실제 메모리 할당 로직을 완성하게 됩니다.
구체적으로는 다음과 같은 작업을 진행하게 됩니다.
- 요청한 크기를 16바이트 정렬에 맞춰 조정한다.
- 힙에서 적당한 Free Block을 찾는다.
- 찾으면 배치하고, 없으면 힙을 확장한 후 다시 배치한다.
다시말해, 요청된 크기에 맞는 메모리 공간을 찾아서 할당해주는 메인 함수입니다.
mm_malloc 구현하기
void *mm_malloc(size_t size)
{
size_t asize; // 정렬을 고려한 블록 크기
size_t extendsize; // 힙을 확장할 크기
char *bp;
// 0 바이트 요청은 무시
if (size == 0) {
return NULL;
}
// 요청한 크기를 조정해서 최소 블록 크기(32바이트) 이상으로 만들기
if (size <= DSIZE) {
asize = 2 * DSIZE; // 최소 32바이트
} else {
// (요청 크기 + 헤더/푸터 크기)를 더블워드(16바이트) 단위로 올림
asize = DSIZE * ((size + (DSIZE) + (DSIZE - 1)) / DSIZE);
}
// 적당한 Free Block 찾기
if ((bp = find_fit(asize)) != NULL) {
place(bp, asize); // 찾은 블록에 할당
return bp;
}
// 만약 적당한 블록이 없다면 힙을 확장하고 다시 할당
extendsize = MAX(asize, CHUNKSIZE); // 요청 크기와 기본 확장 크기 중 더 큰 걸 선택
if ((bp = extend_heap(extendsize / WSIZE)) == NULL) {
return NULL; // 힙 확장 실패
}
place(bp, asize); // 확장한 블록에 할당
return bp;
}
메모리 해제 함수 (mm_free)
mm_free 함수는 사용자가 할당받았던 메모리 블록을 다시 해제하는 함수입니다. 단순히 해당 블록의 헤더와 푸터를 'Free' 상태로 표시하고, 인접한 Free Block들과 병합(coalesce)해줍니다.
구체적으로는 다음과 같은 작업을 진행하게 됩니다.
- 주어진 블록의 헤더/푸터를 '할당 안 됨(0)'으로 표시한다.
- 주변 블록들과 합칠 수 있으면 coalesce 함수로 병합한다.
즉, 메모리를 반납하고, 빈 공간을 주변과 합쳐서 관리하는 함수라고 할 수 있습니다.
mm_free 구현하기
void mm_free(void *ptr)
{
size_t size = GET_SIZE(HDRP(ptr)); // 현재 블록의 크기 가져오기
// 현재 블록의 헤더와 푸터를 Free(0) 상태로 변경
PUT(HDRP(ptr), PACK(size, 0));
PUT(FTRP(ptr), PACK(size, 0));
// 주변 블록과 병합(coalesce) 시도
coalesce(ptr);
}
메모리 재할당 함수 (mm_realloc)
mm_realloc 함수는 이미 할당된 블록의 크기를 변경하는 함수입니다. 예를 들어, 기존에 32바이트를 썼는데 더 큰 64바이트가 필요하거나, 반대로 16바이트로 줄이고 싶을 때 사용하는 거죠.
구체적으로는 다음과 같은 작업을 진행하게 됩니다.
- 요청된 크기가 작으면 기존 블록을 그대로 쓰거나 줄인다.
- 요청된 크기가 크면, 필요에 따라 옆 블록과 병합하거나 새로 할당해서 데이터를 복사한다.
한마디로, 기존 블록 크기를 조정하고, 필요 시 새 공간으로 옮겨주는 함수입니다.
mm_realloc 구현하기
void *mm_realloc(void *ptr, size_t size)
{
if (ptr == NULL) {
return mm_malloc(size); // NULL 포인터라면 malloc처럼 동작
}
if (size == 0) {
mm_free(ptr); // 크기 0 요청은 블록 해제
return NULL;
}
size_t old_block = GET_SIZE(HDRP(ptr)); // 기존 블록의 총 크기
size_t old_payload = old_block - DSIZE; // 데이터만 담을 수 있는 크기
size_t new_asize; // 새로 할당해야 할 블록의 크기
if (size <= DSIZE) {
new_asize = 2 * DSIZE; // 최소 16바이트
} else {
new_asize = DSIZE * ((size + (DSIZE) + (DSIZE - 1)) / DSIZE); // 16바이트 정렬
}
// 요청 크기가 기존 블록보다 작거나 같으면 그대로 사용
if (new_asize <= old_block) {
place(ptr, new_asize); // 필요하면 블록을 쪼갠다
return ptr;
}
// 다음 블록이 Free이고, 합쳤을 때 충분히 크면 병합해서 사용
if (!GET_ALLOC(HDRP(NEXT_BLKP(ptr))) &&
old_block + GET_SIZE(HDRP(NEXT_BLKP(ptr))) >= new_asize) {
size_t total = old_block + GET_SIZE(HDRP(NEXT_BLKP(ptr)));
PUT(HDRP(ptr), PACK(total, 0)); // 새 크기로 헤더 갱신
PUT(FTRP(ptr), PACK(total, 0)); // 새 크기로 푸터 갱신
place(ptr, new_asize); // 다시 할당
return ptr;
}
// 둘 다 안 되면 새 블록을 할당하고, 기존 데이터를 복사
void *new_ptr = mm_malloc(size);
if (new_ptr == NULL) {
return NULL;
}
// 기존 블록의 페이로드 크기가 새로 요청한 크기보다 작으면,
// 기존 블록 크기만큼만 복사. 그렇지 않으면 새로 요청한 크기만큼 복사
size_t copy;
if (old_payload < size) {
copy = old_payload;
} else {
copy = size;
}
// 새로 할당한 메모리(new_ptr)에,
// 기존 메모리(ptr) 내용을 copy 바이트 만큼 복사한다.
memcpy(new_ptr, ptr, copy);
mm_free(ptr); // 기존 메모리 해제
return new_ptr; // 새 블록 포인터 반환
}
마치면서
지금까지 implicit free list 기반으로 동적 메모리 할당기를 구현해보았는데요. 처음엔 단순해 보이지만, coalesce나 realloc처럼 내부 동작을 이해하고 직접 짜보면 메모리 관리의 복잡성과 최적화 포인트를 체감할 수 있을 것입니다.
다음에는 이 기본기를 바탕으로 성능을 훨씬 끌어올릴 수 있는 Explicit Free List 기반 할당기 구현으로 찾아뵙겠습니다. 감사합니다.
'크래프톤 정글 > Code 정글(C언어)' 카테고리의 다른 글
| [Malloc] (참고용) Segregated Free List 기반 동적 할당기 구현하기 (0) | 2025.04.28 |
|---|---|
| [Malloc] Explicit Free List 기반 동적 할당기 구현하기 + 최적화하기 (0) | 2025.04.27 |
| [RBTree] set 기반 RBTree를 multiset 기반으로 전환하기 (0) | 2025.04.24 |
| [RBTree] 삭제 구현하기 (erase_fixup, rbtree_erase) (0) | 2025.04.21 |
| [RBTree] 탐색 및 최솟값/최댓값 함수 구현하기 (rbtree_find, rbtree_min, rbtree_max) (0) | 2025.04.21 |