explicit free list로 옮길 때 실제로 바뀌는 것
기존 implicit 구조를 최대한 덜 깨뜨리면서 explicit free list를 붙일 때 코드가 어디서 달라지는지를 따라가는 2편이다.
왜 2편의 핵심은 explicit free list 자체보다 “어디를 어떻게 고쳤는가”에 있나
1편에서 다뤘던 구조는 implicit free list였다. 힙 전체를 순회하면서 free block을 찾는 방식이라 allocator의 기본 문법을 익히기엔 좋지만, 탐색 비용이 크다. 이번 구현은 그 구조를 통째로 갈아엎기보다, free block만 따로 연결해서 보관하는 층을 기존 코드 위에 덧대는 방식으로 바뀌었다. 그래서 2편의 핵심은 “explicit free list가 뭔가”보다 기존 implicit 코드에서 어떤 줄이 달라졌고, 그 줄 때문에 실행 흐름이 어떻게 달라졌는가를 읽는 데 있다.
앞선 글에서 implicit free list, boundary tag, mm_init, mm_malloc, mm_free, coalesce의 기본 흐름을 이미 본 상태를 전제로 한다. 이번 글은 그 위에 “free block에만 next/prev를 심으면 무엇이 달라지는가”를 덧붙인다.
implicit에서 explicit로 넘어가도 헤더/풋터, split, coalesce 자체가 사라지는 건 아니다. 달라지는 건 탐색 대상과 free block을 연결/해제하는 관리 코드다.
find_fit, place, coalesce의 코드가 정확히 어느 줄에서 달라지나바뀐 핵심 아이디어를 한 줄로 말하면
1편의 implicit allocator는 힙 안에 있는 모든 블록을 대상으로 탐색했다. 2편의 explicit allocator는 free block만 따로 연결한 체인을 대상으로 탐색한다. 그래서 2편은 “블록 구조를 새로 배운다”기보다 “같은 블록 구조 위에 free block용 연결 리스트를 얹는다”는 쪽에 가깝다.
find_fit, place, coalesce에 새 책임이 생긴다.2편에서 실제로 바뀐 함수는 어디인가
| 영역 | 1편 implicit에서 하던 일 | 2편 explicit에서 추가된 일 |
|---|---|---|
| 매크로 / 전역 변수 | 헤더/풋터, 인접 블록 계산 | MINBLOCKSIZE, PRED, SUCC, free_listp 추가 |
| 초기화 | 프롤로그/에필로그와 첫 free block 생성 | free list head를 NULL로 시작하고, 이후 첫 free block을 연결 |
| find_fit | 힙 전체를 NEXT_BLKP로 순회 |
free list만 SUCC로 순회 |
| place | 할당 비트 갱신, split | 할당 전 remove, split 후 남은 조각 재삽입 |
| coalesce | 헤더/풋터 병합 | 이웃 free block remove 후 병합, 병합 결과 재삽입 |
먼저, explicit free list가 줄이는 건 “힙 전체 순회”다
implicit free list에서는 find_fit가 프롤로그 뒤부터 에필로그 전까지 블록 전체를 훑는다. 이때 이미 할당된 블록도 전부 지나가야 한다. explicit free list는 이 점만 바꾼다. free block끼리만 따로 체인을 만들고, 탐색도 그 체인에서만 한다. 즉 “할당 정책”보다 먼저 달라지는 건 allocator가 훑는 대상의 범위다.
free block은 이제 “빈 공간”이 아니라 포인터 두 개를 품는 구조체가 된다
explicit free list로 넘어가면 free block payload는 그냥 버려진 빈 공간이 아니다. 그 안에 이전 free block과 다음 free block을 가리키는 포인터를 넣는다. 그래서 최소 블록 크기가 커진다. 현재 구현도 이 점을 반영해서 MINBLOCKSIZE를 따로 정의한다.
if ((csize - asize) >= (2 * DSIZE)) {
...
}#define MINBLOCKSIZE ALIGN(DSIZE + 2 * sizeof(void *))
if ((csize - asize) >= MINBLOCKSIZE) {
...
}pred, succ를 실제로 심을 수 있는지까지 포함한 기준으로 바뀐다.#define MINBLOCKSIZE ALIGN(DSIZE + 2 * sizeof(void *))
#define PRED(bp) (*(void **)(bp))
#define SUCC(bp) (*(void **)((char *)(bp) + sizeof(void *)))
static void *free_listp;새로 생긴 건 딱 두 함수지만, 이 둘이 흐름 전체를 바꾼다
explicit free list에서 진짜 새로 생기는 건 결국 insert_free_block과 remove_free_block다. 이 둘이 없으면 free list는 한 번도 일관되게 유지되지 않는다. 반대로 말하면, 2편의 핵심은 “allocator 전체를 갈아엎었다”가 아니라 기존 흐름 사이사이에 free list 연결/해제를 끼워 넣었다는 데 있다.
static void insert_free_block(void *bp)
{
PRED(bp) = NULL;
SUCC(bp) = free_listp;
if (free_listp != NULL) {
PRED(free_listp) = bp;
}
free_listp = bp;
}
static void remove_free_block(void *bp)
{
if (PRED(bp) != NULL)
SUCC(PRED(bp)) = SUCC(bp);
else
free_listp = SUCC(bp);
if (SUCC(bp) != NULL)
PRED(SUCC(bp)) = PRED(bp);
}mm_init과 extend_heap은 free list의 출발점을 같이 만든다
기본 힙 경계를 세우는 역할은 1편과 같다. 다만 이제는 free_listp = NULL이 초기화에 들어간다. 또 extend_heap이 만든 새 free block은 그냥 반환되는 게 아니라, 뒤에서 coalesce를 거쳐 free list에 연결된다.
heap_listp = mem_sbrk(...);
...
extend_heap(...);heap_listp = mem_sbrk(...);
free_listp = NULL;
...
extend_heap(...);if ((heap_listp = mem_sbrk(4 * WSIZE)) == (void *)-1)
return -1;
free_listp = NULL;
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));find_fit은 이제 힙이 아니라 free list만 훑는다
이 변화가 explicit free list의 가장 직접적인 보상이다. 기존에는 에필로그까지 가면서 alloc/free를 모두 지나갔다. 이제는 free_listp에서 시작해 SUCC(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;
}
}for (bp = free_listp;
bp != NULL;
bp = SUCC(bp)) {
if (asize <= GET_SIZE(HDRP(bp))) {
return bp;
}
}static void *find_fit(size_t asize) {
void *bp;
for (bp = free_listp; bp != NULL; bp = SUCC(bp)) {
if (asize <= GET_SIZE(HDRP(bp))) {
return bp;
}
}
return NULL;
}프롤로그 뒤부터 에필로그 전까지 계속
NEXT_BLKP로 이동free_listp에서 시작해서 free block끼리만 SUCC로 이동다만 여기서도 중요한 건 “first-fit이 사라졌다”가 아니다. 현재 구현은 여전히 first-fit이다. 단지 first-fit을 적용하는 집합이 힙 전체에서 free list로 줄었을 뿐이다.
place는 이제 배치 함수이면서 리스트 정리 함수다
1편에서는 place가 “헤더/풋터를 할당으로 바꾸고 split할지 말지 결정하는 함수”였다. 지금은 그 앞에 한 줄이 더 붙는다. 배치 대상 free block을 먼저 free list에서 떼야 한다. 그리고 split이 일어나면 새로 남은 free block을 다시 free list에 꽂아야 한다.
PUT(HDRP(bp), PACK(asize, 1));
PUT(FTRP(bp), PACK(asize, 1));
next_bp = NEXT_BLKP(bp);
PUT(HDRP(next_bp), PACK(csize - asize, 0));
PUT(FTRP(next_bp), PACK(csize - asize, 0));remove_free_block(bp);
PUT(HDRP(bp), PACK(asize, 1));
PUT(FTRP(bp), PACK(asize, 1));
next_bp = NEXT_BLKP(bp);
PUT(HDRP(next_bp), PACK(csize - asize, 0));
PUT(FTRP(next_bp), PACK(csize - asize, 0));
insert_free_block(next_bp);static void place(void *bp, size_t asize) {
size_t csize = GET_SIZE(HDRP(bp));
remove_free_block(bp);
if ((csize - asize) >= MINBLOCKSIZE) {
void *next_bp;
PUT(HDRP(bp), PACK(asize, 1));
PUT(FTRP(bp), PACK(asize, 1));
next_bp = NEXT_BLKP(bp);
PUT(HDRP(next_bp), PACK(csize - asize, 0));
PUT(FTRP(next_bp), PACK(csize - asize, 0));
insert_free_block(next_bp);
} else {
PUT(HDRP(bp), PACK(csize, 1));
PUT(FTRP(bp), PACK(csize, 1));
}
}coalesce는 이제 병합 함수이면서 링크 복구 함수다
explicit free list로 바뀐 뒤 가장 중요해진 함수는 coalesce다. 1편에서는 크기와 경계만 맞추면 됐다. 이제는 다르다. 병합 대상인 이웃 free block이 free list 안에 이미 들어가 있으므로, 먼저 체인에서 떼고 병합해야 한다. 그 뒤 병합 결과 블록을 다시 free list에 넣어야 일관성이 유지된다.
size += ...;
PUT(HDRP(...), PACK(size, 0));
PUT(FTRP(...), PACK(size, 0));
bp = PREV_BLKP(bp);remove_free_block(PREV_BLKP(bp));
remove_free_block(NEXT_BLKP(bp));
size += ...;
PUT(HDRP(...), PACK(size, 0));
PUT(FTRP(...), PACK(size, 0));
bp = PREV_BLKP(bp);
insert_free_block(bp);if (prev_alloc && next_alloc) {
insert_free_block(bp);
return bp;
}
else if (prev_alloc && !next_alloc) {
remove_free_block(NEXT_BLKP(bp));
...
}
else if (!prev_alloc && next_alloc) {
remove_free_block(PREV_BLKP(bp));
...
}
else {
remove_free_block(PREV_BLKP(bp));
remove_free_block(NEXT_BLKP(bp));
...
}
insert_free_block(bp);mm_malloc은 실제로 크게 안 바뀌지만, 한 줄이 allocator의 성격을 바꾼다
겉으로 보면 mm_malloc은 1편과 비슷하다. 요청 크기를 조정하고, 맞는 블록을 찾고, 없으면 확장한다. 그런데 여기엔 두 가지 명확한 변화가 있다. 하나는 MINBLOCKSIZE를 기준으로 split 여부를 판단한다는 점, 다른 하나는 find_fit가 더 이상 힙 전체를 보지 않는다는 점이다.
asize = MAX(ALIGN(size + DSIZE), MINBLOCKSIZE);
if ((bp = find_fit(asize)) != NULL) {
place(bp, asize);
return bp;
}| 항목 | 1편 implicit | 2편 explicit |
|---|---|---|
| 탐색 대상 | 힙 전체 블록 | free block 체인 |
| 최소 블록 크기 기준 | 2 * DSIZE 수준 |
MINBLOCKSIZE를 따로 둠 |
| split 후 남은 조각 | 헤더/풋터만 맞추면 됨 | 헤더/풋터 + free list 재삽입 필요 |
이 구현은 “최소 수정”이라는 장점과 한계를 함께 가진다
지금 코드의 장점은 분명하다. implicit 구조의 블록 문법을 거의 그대로 유지한 채 explicit free list만 붙였다. 그래서 변화 지점을 추적하기 쉽고, 디버깅도 덜 복잡하다. 반대로 한계도 분명하다. free list 정렬 정책, best-fit 여부, realloc 최적화, 더 세밀한 split 정책은 아직 손대지 않았다. 즉 이 구현은 “완성형 explicit allocator”라기보다 implicit 기반 코드를 explicit로 옮기는 첫 안정 단계에 가깝다.
직접 해볼 실습
- LIFO insertion이면 head가 어떻게 바뀌는지 적는다.
PRED,SUCC가 각 블록에서 어떤 값을 가리키는지 적는다.- B를 remove할 때 어느 링크 두 개가 바뀌는지 적는다.
explicit free list는 결국 “힙 메타데이터 + 포인터 체인” 두 구조를 동시에 맞춰야 한다는 점을 직접 느껴 본다.
- 먼저 할당 대상 블록을 리스트에서 제거한다.
- 앞부분을 allocated block으로 바꾼다.
- 남은 조각이
MINBLOCKSIZE이상이면 새 free block으로 만든다. - 그 free block을 다시 list head에 꽂는다.
split은 메모리 절약 문제가 아니라, free list 일관성을 다시 세우는 문제라는 점이 보이면 제대로 읽은 것이다.
- explicit free list는 allocator 문법을 새로 만드는 게 아니라, free block만 따로 연결하는 관리 층을 추가하는 구조다.
- free block payload 안에 포인터 둘을 심기 때문에 최소 블록 크기가 커진다.
find_fit는 여전히 first-fit일 수 있지만, 탐색 대상은 힙 전체가 아니라 free list다.place는 배치 함수이면서 동시에 free list 정리 함수가 된다.coalesce는 병합 전에 이웃을 떼고, 병합 후 결과를 다시 넣어야 한다.
coalesce에서 이웃 블록을 먼저 remove하지 않으면 어떤 종류의 버그가 생기는가?'크래프톤 정글 > 정글에서 문제풀기' 카테고리의 다른 글
| Malloc Lab 구현기 3편 - explicit free list에서 segregated free list로 바꾸며 달라진 것 (0) | 2026.04.14 |
|---|---|
| Malloc Lab을 활용한 Implicit Free List 구현기 (1) | 2026.04.13 |
| 이진 탐색 트리 Q5. 두 개의 스택으로 후위 순회하기 (0) | 2026.04.09 |
| 이진 탐색 트리 Q4. 한 개의 스택으로 후위 순회하기 (0) | 2026.04.09 |
| 이진 탐색 트리 Q3. 반복문으로 전위 순회하기 (0) | 2026.04.09 |