CS:APP 9장 가상메모리 & Malloc C언어로 구현
C언어로 직접 Malloc을 구현해보자
- 1. Malloc 할당 개요
- 2. 핵심 용어
- 3. 블록 설계 기초
- 4. 묵시적 리스트 (Implicit List)
- 5. 명시적 리스트 (Explicit List)
- 6. 명시적 리스트 Refactoring
말록 구현에 앞서 명시적 할당자(Explicit allocator) 와 묵시적 할당자(Implicit allocator) 를 구분해두자. 둘의 차이는 free를 누가, 직접/간접 중 어느 방식으로 수행하느냐에 있다.
| 구분 | Explicit allocator | Implicit allocator |
|---|---|---|
| free 방식 | 프로그래머가 직접 호출 | 시스템이 간접적으로 회수 |
| 사용 예 | C의 malloc / free |
Java의 garbage collection, ML, Lisp |
malloc의 기본 개념은 이전 포스팅 동적 메모리 할당(Dynamic memory allocation)을 참조하면 된다. 이 글에서는 Explicit allocator인 malloc을 직접 구현한다.
1. Malloc 할당 개요
위 사진의 할당/해제 순서는 다음과 같다.
| 순서 | 동작 |
|---|---|
| 1 | p1 할당 (int × 4) |
| 2 | p2 할당 (int × 5) |
| 3 | p3 할당 (int × 6) |
| 4 | p2 free |
| 5 | p4 할당 (int × 2) |
응용 프로그램의 자유
- 응용 프로그램은
malloc과free를 마음대로 요청할 수 있다 - 단,
free는 반드시malloc된 블록에 대해서만 가능하다
Allocator의 제약
명시적 할당자는 다음의 엄격한 제한 안에서 동작해야 한다.
- 할당된 블록의 개수·크기를 관리할 권한이 없다
malloc요청에 즉시 응답해야 한다 (나중으로 미룰 수 없다)- free된 메모리에서만 할당할 수 있다
- 정렬 요구사항을 지켜야 한다 (리눅스 기준 x86: 8byte, x86-64: 16byte)
- free 블록만 조작할 수 있다
- 한 번 할당된 블록은 이동할 수 없다 (= 압축 불가)
2. 핵심 용어
| 용어 | 설명 |
|---|---|
| Throughput | 시간당 완료된 요청 수 (5000 malloc + 5000 free를 10초에 끝내면 1000 ops/sec) |
| Payload | 블록 안에서 실제로 사용하는 데이터 |
| Overhead | 블록 안에서 payload를 제외한 나머지 (header, footer, padding) |
| Aggregate payload | 할당된 블록들의 데이터 총합 |
| Peak utilization | 할당기가 힙을 얼마나 효율적으로 쓰는지를 나타내는 지표 (높을수록 좋음) |
최고 이용도는 다음과 같이 정의한다. $P_i$는 시점 $i$까지의 할당된 데이터 합, $H_k$는 현재 힙 크기다.
\[U_k = \frac{\max_{i \le k} P_i}{H_k}\]단편화 두 종류
| 종류 | 원인 | 설명 |
|---|---|---|
| 내부 단편화 (Internal) | overhead, padding | 블록 내부 공간을 효율적으로 못 쓰는 것 |
| 외부 단편화 (External) | 가용 블록의 분산 | 가용 블록 총합은 충분하지만, 적당한 크기의 연속 블록이 없는 것 |
3. 블록 설계 기초
3-1. Header의 탄생
포인터로 블록과 블록을 건너뛰려면 “payload가 어디서 시작하고 어디까지 읽어야 하는가”를 알아야 한다. 그래서 header라는 overhead에 블록 크기를 저장하자는 아이디어가 나왔다.
- header 덕분에 각 블록의 시작점을 순차적으로 탐색할 수 있게 됐다
- 책에서는 payload 시작 주소를 기준으로, 그 앞에 overhead(header) 를 두기로 했다
- 그런데 태초의 첫 주소는 앞에 공간이 없어 header를 못 넣는다 → 그래서 첫 주소에는 항상 padding을 넣어준다
추가로, 블록이 가용인지 비가용인지도 구분해야 한다. 이미 할당된 블록에 또 할당하면 안 되기 때문이다.
정렬(32bit→8byte, 64bit→16byte) 때문에 블록 크기의 하위 3~4bit는 항상 0으로 남는다. 이 남는 비트를 활용하자.
- overhead를 읽을 때 하위 3~4bit를 제외하고 읽으면 블록 크기, 그 비트들만 따로 읽으면 부가 정보가 된다
- 책에서는 32bit 시스템(3bit 남음)을 사용해, 가장 첫 번째 비트에 가용/비가용(1/0) 을 저장한다
3-2. Footer의 탄생
할당과 free를 반복하면 free 블록이 연속될 수 있다. 아래 사진처럼 4-size와 2-size 가용 블록이 붙어 있는데 5-size를 할당하려 하면, “할당 크기보다 같거나 큰 블록을 찾는” 코드 특성상 할당에 실패한다(외부 단편화).
이 코드를 유지하면서 해결하는 방향은 다음과 같다.
- 연속된 가용 블록이 생기지 않게 한다 — 연속된 가용 블록이 없으면 아쉬울 일이 없다
- free 시 앞뒤 가용 블록을 병합(coalesce)한다
- 뒤 블록은 현재 header 크기를 더해 위치를 알 수 있다
- 앞 블록은 크기를 모른다 → footer를 도입해 블록 뒤에 크기·가용 정보를 저장한다
- (extra) footer도 overhead라 없는 게 좋다. 모든 블록에 footer가 필요할까?
- 남는 3~4bit에 앞 블록의 가용/비가용 정보를 함께 넣으면, footer는 가용 블록에만 필요하고 할당된 블록에는 불필요해진다
4. 묵시적 리스트 (Implicit List)
4-1. First-fit
CS:APP 교재 기반의 묵시적 리스트 + first-fit 구현이다.
/*
* mm-naive.c - The fastest, least memory-efficient malloc package.
*
* In this naive approach, a block is allocated by simply incrementing
* the brk pointer. A block is pure payload. There are no headers or
* footers. Blocks are never coalesced or reused. Realloc is
* implemented directly using mm_malloc and mm_free.
*
* NOTE TO STUDENTS: Replace this header comment with your own header
* comment that gives a high level description of your solution.
*/
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <unistd.h>
#include <string.h>
#include "mm.h"
#include "memlib.h"
team_t team = {
"ateam",
"Harry Bovik",
"bovik@cs.cmu.edu",
"",
""};
/* single word (4) or double word (8) alignment */
#define ALIGNMENT 8
#define WSIZE 4 /* header/footer size */
#define DSIZE 8 /* double word size */
#define CHUNKSIZE (1 << 12) /* Extend heap by this amount (bytes) */
#define MAX(x, y) ((x) > (y) ? (x) : (y))
/* Pack a size and allocated bit into a word */
#define PACK(size, alloc) ((size) | (alloc))
/* Read and write a word at address p */
#define GET(p) (*(unsigned int *)(p))
#define PUT(p, val) (*(unsigned int *)(p) = (val))
/* Read the size and allocated fields from address p */
#define GET_SIZE(p) (GET(p) & ~0x7)
#define GET_ALLOC(p) (GET(p) & 0x1)
/* Given block ptr bp, compute address of its header and footer */
#define HDRP(bp) ((char *)(bp) - WSIZE)
#define FTRP(bp) ((char *)(bp) + GET_SIZE(HDRP(bp)) - DSIZE)
/* Given block ptr bp, compute address of next and previous blocks */
#define NEXT_BLKP(bp) ((char *)(bp) + GET_SIZE(((char *)(bp)-WSIZE)))
#define PREV_BLKP(bp) ((char *)(bp) - GET_SIZE(((char *)(bp)-DSIZE)))
/* rounds up to the nearest multiple of ALIGNMENT */
#define ALIGN(size) (((size) + (ALIGNMENT - 1)) & ~0x7)
#define SIZE_T_SIZE (ALIGN(sizeof(size_t)))
static char *heap_listp;
int mm_init(void);
static void *extend_heap(size_t words);
static void *find_fit(size_t asize);
static void place(void *bp, size_t asize);
static void *coalesce(void *bp);
int mm_init(void)
{
/* Create the initial empty heap */
if ((heap_listp = mem_sbrk(4*WSIZE)) == (void *)-1)
return -1;
PUT(heap_listp, 0);
PUT(heap_listp + (1*WSIZE), PACK(DSIZE, 1));
PUT(heap_listp + (2*WSIZE), PACK(DSIZE, 1));
PUT(heap_listp + (3*WSIZE), PACK(0, 1));
heap_listp += (2*WSIZE);
/* Extend the empty heap with a free block of CHUNKSIZE bytes */
if (extend_heap(CHUNKSIZE/WSIZE) == NULL)
return -1;
return 0;
}
static void *extend_heap(size_t words)
{
char *bp;
size_t size;
/* Allocate an even number of words to maintain alignment */
size = (words % 2) ? (words + 1) * WSIZE : words * WSIZE;
if ((long)(bp = mem_sbrk(size)) == -1)
return NULL;
/* Initialize free block header/footer and the epilogue header */
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 epilogue header */
/* Coalesce if the previous block was free */
return coalesce(bp);
}
void *mm_malloc(size_t size)
{
size_t asize;
size_t extendsize;
char * bp;
/* Ignore spurious requests */
if (size == 0)
return NULL;
/* Adjust block size to include overhead and alignment reqs. */
if (size <= DSIZE)
asize = 2 * DSIZE;
else
asize = DSIZE * ((size + DSIZE + (DSIZE - 1)) / DSIZE);
/* Search the free list for a fit */
if ((bp = find_fit(asize)) != NULL)
{
place(bp, asize);
return bp;
}
/* No fit found. Get more memory and place the block */
extendsize = MAX(asize, CHUNKSIZE);
if ((bp = extend_heap(extendsize/WSIZE)) == NULL)
return NULL;
place(bp, asize);
return bp;
}
static void *find_fit(size_t asize)
{
/* First-fit search */
void *bp;
for (bp = heap_listp; GET_SIZE(HDRP(bp)) > 0; bp = NEXT_BLKP(bp))
{
if (!GET_ALLOC(HDRP(bp)) && (asize <= GET_SIZE(HDRP(bp))))
{
return bp;
}
}
return NULL;
}
static void place(void *bp, size_t asize)
{
size_t csize = GET_SIZE(HDRP(bp));
if ((csize - asize) >= (2*DSIZE))
{
PUT(HDRP(bp), PACK(asize, 1));
PUT(FTRP(bp), PACK(asize, 1));
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));
}
}
void mm_free(void *ptr)
{
size_t size = GET_SIZE(HDRP(ptr));
PUT(HDRP(ptr), PACK(size, 0)); /* 헤더를 미할당 상태로 update */
PUT(FTRP(ptr), PACK(size, 0)); /* 푸터를 미할당 상태로 update */
coalesce(ptr); /* free 끼리 병합 */
}
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));
if (prev_alloc && next_alloc)
return bp;
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));
}
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);
}
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;
}
void *mm_realloc(void *ptr, size_t size)
{
void *oldptr = ptr;
void *newptr;
size_t copySize;
newptr = mm_malloc(size);
if (newptr == NULL)
return NULL;
copySize = *(size_t *)((char *)oldptr - SIZE_T_SIZE);
if (size < copySize)
copySize = size;
memcpy(newptr, oldptr, copySize);
mm_free(oldptr);
return newptr;
}
이 코드의 실행 결과는 아래와 같다.
4-2. Next-fit
묵시적 방식에서 가장 빠르다는 next-fit을 구현해봤다. next_ptr 전역변수를 두고, 마지막으로 찾은 위치부터 탐색을 이어가는 방식이다. 바뀐 부분만 정리했다.
static void *next_ptr = NULL; // 전역변수로 선언
static void *extend_heap(size_t words)
{
char *bp;
size_t size;
size = (words % 2) ? (words + 1) * WSIZE : words * WSIZE;
if ((long)(bp = mem_sbrk(size)) == -1)
return NULL;
PUT(HDRP(bp), PACK(size, 0));
PUT(FTRP(bp), PACK(size, 0));
PUT(HDRP(NEXT_BLKP(bp)), PACK(0, 1));
next_ptr = bp; /* Set next_ptr to the new block */
return coalesce(bp);
}
static void *find_fit(size_t asize)
{
void *bp;
for (bp = next_ptr; GET_SIZE(HDRP(bp)) > 0; bp = NEXT_BLKP(bp))
{
if (!GET_ALLOC(HDRP(bp)) && (asize <= GET_SIZE(HDRP(bp))))
{
next_ptr = bp;
return bp;
}
}
return NULL;
}
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));
if (prev_alloc && next_alloc)
return bp;
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));
}
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);
}
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);
}
next_ptr = bp;
return bp;
}
coalesce에서 free한 블록에 next_ptr을 넣는 것은 엄밀히는 next-fit 개념에 어긋나지만, 테스트 케이스가 많은 편이어서 이렇게 진행했다. 결과적으로 점수가 21점 올랐다.
5. 명시적 리스트 (Explicit List)
마지막으로 명시적 리스트를 구현했다. 가용 블록끼리 이중 연결 리스트로 묶어 find_fit이 free 블록만 순회하도록 한 방식이다.
핵심은 payload 공간에 다음/이전 free 블록을 가리키는 포인터를 저장하는 매크로다.
NEXT_FREE(bp):bp를 이중 포인터로 형변환해 역참조 → bp가 가리키는 메모리에 저장된 “다음 free 블록 포인터”를 읽고 쓴다PREV_FREE(bp): 같은 원리지만bp + PTR_SIZE위치에 “이전 free 블록 포인터”를 저장한다SET_NEXT_FREE/SET_PREV_FREE: 위 위치에 실제 주소값을 써넣는다
/* (생략된 헤더 주석/include/team_t는 위와 동일) */
/* single word (4) or double word (8) alignment */
#define ALIGNMENT 16
#define WSIZE 4 /* header/footer size */
#define PTR_SIZE sizeof(void *) /* pointer size */
#define MIN_FREE_BLOCK_SIZE (WSIZE + PTR_SIZE + PTR_SIZE + WSIZE)
#define CHUNKSIZE (1 << 12)
#define MAX(x, y) ((x) > (y) ? (x) : (y))
#define PACK(size, alloc) ((size) | (alloc))
#define GET(p) (*(unsigned int *)(p))
#define PUT(p, val) (*(unsigned int *)(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)) - (WSIZE*2))
#define NEXT_BLKP(bp) ((char *)(bp) + GET_SIZE(((char *)(bp)-WSIZE)))
#define PREV_BLKP(bp) ((char *)(bp) - GET_SIZE(((char *)(bp)-(WSIZE*2))))
/* free list 포인터 매크로 (payload 공간에 next/prev free 포인터 저장) */
#define NEXT_FREE(bp) (*(void **)(bp))
#define PREV_FREE(bp) (*(void **)((char *)(bp) + PTR_SIZE))
#define SET_NEXT_FREE(bp, ptr) (NEXT_FREE(bp) = (ptr))
#define SET_PREV_FREE(bp, ptr) (PREV_FREE(bp) = (ptr))
#define ALIGN(size) (((size) + (ALIGNMENT - 1)) & ~0xf)
#define SIZE_T_SIZE (ALIGN(sizeof(size_t)))
static void *free_root = NULL; /* Pointer to the first free block */
static char *heap_listp;
static void add_to_free_list(void *bp);
static void remove_from_free_list(void *bp);
int mm_init(void);
static void *extend_heap(size_t words);
static void *find_fit(size_t asize);
static void place(void *bp, size_t asize);
static void *coalesce(void *bp);
int mm_init(void)
{
if ((heap_listp = mem_sbrk(4*WSIZE)) == (void *)-1)
return -1;
PUT(heap_listp, 0);
PUT(heap_listp + (1*WSIZE), PACK((WSIZE*2), 1));
PUT(heap_listp + (2*WSIZE), PACK((WSIZE*2), 1));
PUT(heap_listp + (3*WSIZE), PACK(0, 1));
heap_listp += (2*WSIZE);
free_root = NULL;
if (extend_heap(CHUNKSIZE/WSIZE) == NULL)
return -1;
return 0;
}
static void *extend_heap(size_t words)
{
char *bp;
size_t size;
size = (words * WSIZE); // words는 WSIZE 단위
size = ALIGN(size); // 최종 크기를 16의 배수로 올림
if ((long)(bp = mem_sbrk(size)) == -1)
return NULL;
PUT(HDRP(bp), PACK(size, 0));
PUT(FTRP(bp), PACK(size, 0));
PUT(HDRP(NEXT_BLKP(bp)), PACK(0, 1));
return coalesce(bp); // free_root 설정/포인터 초기화는 coalesce에서 처리
}
void *mm_malloc(size_t size)
{
size_t asize;
size_t extendsize;
char * bp;
if (size == 0)
return NULL;
size_t needed = size + (WSIZE * 2);
if (needed <= MIN_FREE_BLOCK_SIZE)
asize = MIN_FREE_BLOCK_SIZE;
else
asize = ALIGN(needed);
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;
}
static void *find_fit(size_t asize)
{
/* First-fit search (free list만 순회) */
void *bp;
for (bp = free_root; bp != NULL; bp = NEXT_FREE(bp))
{
if (asize <= GET_SIZE(HDRP(bp))) // 크기만 비교
{
return bp;
}
}
return NULL;
}
static void place(void *bp, size_t asize)
{
size_t csize = GET_SIZE(HDRP(bp));
remove_from_free_list(bp); // 먼저 free list에서 제거
if ((csize - asize) >= (MIN_FREE_BLOCK_SIZE)) // 분할 가능
{
PUT(HDRP(bp), PACK(asize, 1));
PUT(FTRP(bp), PACK(asize, 1));
void *next_bp = NEXT_BLKP(bp);
PUT(HDRP(next_bp), PACK(csize - asize, 0));
PUT(FTRP(next_bp), PACK(csize - asize, 0));
add_to_free_list(next_bp); // 남은 free 블록 다시 추가
}
else // 분할 불가 (전체 사용)
{
PUT(HDRP(bp), PACK(csize, 1));
PUT(FTRP(bp), PACK(csize, 1));
}
}
void mm_free(void *ptr)
{
size_t size = GET_SIZE(HDRP(ptr));
PUT(HDRP(ptr), PACK(size, 0));
PUT(FTRP(ptr), PACK(size, 0));
coalesce(ptr);
}
static void *coalesce(void *bp)
{
void *prev_blk = PREV_BLKP(bp);
void *next_blk = NEXT_BLKP(bp);
size_t prev_alloc = GET_ALLOC(FTRP(prev_blk));
size_t next_alloc = GET_ALLOC(HDRP(next_blk));
size_t size = GET_SIZE(HDRP(bp));
// Case 1: 병합 불필요
if (prev_alloc && next_alloc) {
add_to_free_list(bp);
return bp;
}
// Case 2: 다음 블록과 병합
else if (prev_alloc && !next_alloc) {
remove_from_free_list(next_blk);
size += GET_SIZE(HDRP(next_blk));
PUT(HDRP(bp), PACK(size, 0));
PUT(FTRP(bp), PACK(size, 0));
add_to_free_list(bp);
return bp;
}
// Case 3: 이전 블록과 병합
else if (!prev_alloc && next_alloc) {
remove_from_free_list(prev_blk);
size += GET_SIZE(HDRP(prev_blk));
bp = prev_blk;
PUT(HDRP(bp), PACK(size, 0));
PUT(FTRP(bp), PACK(size, 0));
add_to_free_list(bp);
return bp;
}
// Case 4: 양쪽 모두 병합
else {
remove_from_free_list(prev_blk);
remove_from_free_list(next_blk);
size += GET_SIZE(HDRP(prev_blk)) + GET_SIZE(HDRP(next_blk));
bp = prev_blk;
PUT(HDRP(bp), PACK(size, 0));
PUT(FTRP(bp), PACK(size, 0));
add_to_free_list(bp);
return bp;
}
}
void *mm_realloc(void *ptr, size_t size)
{
void *oldptr = ptr;
void *newptr;
size_t copySize;
newptr = mm_malloc(size);
if (newptr == NULL)
return NULL;
copySize = GET_SIZE(HDRP(oldptr)) - (WSIZE*2);
if (size < copySize)
copySize = size;
memcpy(newptr, oldptr, copySize);
mm_free(oldptr);
return newptr;
}
// --- Helper 함수 ---
// Free list 맨 앞에 블록 추가 (LIFO)
static void add_to_free_list(void *bp) {
if (free_root == NULL) {
SET_NEXT_FREE(bp, NULL);
SET_PREV_FREE(bp, NULL);
free_root = bp;
} else {
SET_NEXT_FREE(bp, free_root);
SET_PREV_FREE(bp, NULL);
SET_PREV_FREE(free_root, bp);
free_root = bp;
}
}
// Free list에서 블록 제거
static void remove_from_free_list(void *bp) {
void *prev_free = PREV_FREE(bp);
void *next_free = NEXT_FREE(bp);
if (prev_free == NULL) { // bp가 첫 번째 블록
free_root = next_free;
} else {
SET_NEXT_FREE(prev_free, next_free);
}
if (next_free != NULL) { // bp가 마지막 블록이 아님
SET_PREV_FREE(next_free, prev_free);
}
}
결과는 1점이 더 올랐다. 명시적 리스트에서는 메모리 효율 면에서 best-fit이 가장 좋다.
6. 명시적 리스트 Refactoring
처음엔 명시적 리스트의 포인터 변경을 coalesce 안에서 직접 다 처리했는데, 이게 꽤 복잡했다. 그 개선 과정을 정리한다.
명시적 리스트는 가용 블록의 포인터 생성/변경을 고려해야 하는데, 특히 양쪽 병합인 Case 4는 포인터를 8개나 다뤄야 한다.
그래서 초기 코드는 아래처럼 case마다 포인터를 일일이 갱신하는 형태로 비대해졌다.
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));
void *prev_free_root;
void *prev_free_root_prev;
void *next_free_blk_next;
void *next_free_blk_prev;
void *prev_free_blk_next;
void *prev_free_blk_prev;
if (prev_alloc && next_alloc) // Case 1
{
if (free_root == NULL)
{
free_root = bp;
SET_NEXT_FREE(bp, NULL);
SET_PREV_FREE(bp, NULL);
}
else
{
prev_free_root = free_root;
SET_PREV_FREE(prev_free_root, bp);
SET_NEXT_FREE(bp, prev_free_root);
SET_PREV_FREE(bp, NULL);
free_root = bp;
}
}
else if (prev_alloc && !next_alloc) // Case 2
{
size += GET_SIZE(HDRP(NEXT_BLKP(bp)));
PUT(HDRP(bp), PACK(size, 0));
PUT(FTRP(bp), PACK(size, 0));
if (free_root == NULL)
{
free_root = bp;
SET_NEXT_FREE(bp, NULL);
SET_PREV_FREE(bp, NULL);
}
else
{
prev_free_root = free_root;
prev_free_root_prev = PREV_FREE(free_root);
next_free_blk_next = NEXT_FREE(NEXT_BLKP(bp));
next_free_blk_prev = PREV_FREE(NEXT_BLKP(bp));
SET_NEXT_FREE(next_free_blk_prev, next_free_blk_next);
SET_PREV_FREE(next_free_blk_next, next_free_blk_prev);
SET_NEXT_FREE(bp, prev_free_root);
SET_PREV_FREE(bp, NULL);
SET_PREV_FREE(prev_free_root_prev, bp);
free_root = bp;
}
}
else if (!prev_alloc && next_alloc) // Case 3
{
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);
if (free_root == NULL)
{
free_root = bp;
SET_NEXT_FREE(bp, NULL);
SET_PREV_FREE(bp, NULL);
}
else
{
prev_free_root = free_root;
prev_free_root_prev = PREV_FREE(free_root);
prev_free_blk_next = NEXT_FREE(PREV_BLKP(bp));
prev_free_blk_prev = PREV_FREE(PREV_BLKP(bp));
SET_NEXT_FREE(prev_free_blk_prev, prev_free_blk_next);
SET_PREV_FREE(prev_free_blk_next, prev_free_blk_prev);
SET_NEXT_FREE(bp, prev_free_root);
SET_PREV_FREE(bp, NULL);
SET_PREV_FREE(prev_free_root_prev, bp);
free_root = bp;
}
}
else // Case 4
{
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);
prev_free_root = free_root;
prev_free_root_prev = PREV_FREE(free_root);
prev_free_blk_next = NEXT_FREE(PREV_BLKP(bp));
prev_free_blk_prev = PREV_FREE(PREV_BLKP(bp));
next_free_blk_next = NEXT_FREE(NEXT_BLKP(bp));
next_free_blk_prev = PREV_FREE(NEXT_BLKP(bp));
SET_NEXT_FREE(prev_free_blk_prev, prev_free_blk_next);
SET_PREV_FREE(prev_free_blk_next, prev_free_blk_prev);
SET_NEXT_FREE(next_free_blk_prev, next_free_blk_next);
SET_PREV_FREE(next_free_blk_next, next_free_blk_prev);
SET_NEXT_FREE(bp, prev_free_root);
SET_PREV_FREE(bp, NULL);
SET_PREV_FREE(prev_free_root_prev, bp);
free_root = bp;
}
free_root = bp;
return bp;
}
포인터 조작을 두 개의 헬퍼 함수로 분리했다.
6-1. 분리한 헬퍼 함수
// Free list 맨 앞에 블록 추가 (LIFO)
static void add_to_free_list(void *bp) {
if (free_root == NULL) {
SET_NEXT_FREE(bp, NULL);
SET_PREV_FREE(bp, NULL);
free_root = bp;
} else {
SET_NEXT_FREE(bp, free_root); // 현재 블록의 next를 기존 첫 free 블록으로
SET_PREV_FREE(bp, NULL); // 현재 블록의 prev는 NULL
SET_PREV_FREE(free_root, bp); // 기존 첫 free 블록의 prev를 현재 블록으로
free_root = bp;
}
}
// Free list에서 블록 제거
static void remove_from_free_list(void *bp) {
void *prev_free = PREV_FREE(bp);
void *next_free = NEXT_FREE(bp);
if (prev_free == NULL) { // bp가 첫 번째 블록
free_root = next_free;
} else {
SET_NEXT_FREE(prev_free, next_free);
}
if (next_free != NULL) { // bp가 마지막 블록이 아님
SET_PREV_FREE(next_free, prev_free);
}
}
각 함수가 담당하는 포인터를 사진 번호로 매핑하면 다음과 같다.
| 함수 | 담당 포인터 |
|---|---|
add_to_free_list |
①, ②, ③, ④ |
remove_from_free_list |
⑤, ⑥, ⑦, ⑧ |
6-2. 개선된 Case 4
덕분에 Case 4가 다음처럼 간결해졌다. 복잡한 포인터 갱신은 모두 헬퍼 함수가 담당한다.
// Case 4: 양쪽 모두 병합
else { // (!prev_alloc && !next_alloc)
remove_from_free_list(prev_blk); // 이전 블록 제거
remove_from_free_list(next_blk); // 다음 블록 제거
size += GET_SIZE(HDRP(prev_blk)) + GET_SIZE(HDRP(next_blk));
bp = prev_blk; // 병합된 블록의 시작으로 이동
PUT(HDRP(bp), PACK(size, 0));
PUT(FTRP(bp), PACK(size, 0));
add_to_free_list(bp); // 최종 병합 블록을 리스트에 추가
return bp;
}
