Malloc Lab 구현기 3편 - explicit free list에서 segregated free list로 바꾸며 달라진 것

MALLOC LAB IMPLEMENTATION GUIDE 03

explicit free list에서
segregated free list로 바꾸며 달라진 것

이번 글은 segregated free list 일반론보다,
2편 explicit allocator 위에 크기 클래스 배열을 얹으면서 어떤 함수와 탐색 흐름이 바뀌는지를 코드 중심으로 따라가는 3편이다.

Segregated Free List Size Class Search Reused Explicit Core find_fit Rewritten

왜 3편의 핵심은 free list를 더 많이 만든다보다 “탐색 시작점을 나눈다”에 있나

2편 explicit free list는 힙 전체를 훑는 implicit 구조보다 훨씬 나았지만, 여전히 free block 전부가 한 체인 안에 있었다. 그래서 큰 블록과 작은 블록이 같은 리스트 안에 섞여 있고, find_fit는 매번 그 체인을 처음부터 더듬어야 했다. 이번 구현은 그 체인을 버리는 게 아니라 크기별로 나눈 여러 head 배열로 바꾸면서, 탐색을 더 작은 후보 집합에서 시작하게 만든다. 즉 3편의 본질은 “free list가 여러 개다”보다 어느 리스트에서 탐색을 시작할지를 결정하는 정책이 코드에 들어온다는 데 있다.

이 글을 읽기 전에 딱 두 가지만 잡으면 된다

1. Malloc Lab은 mm.c 안의 allocator를 구현하고, mdriver가 그 네 함수(mm_init, mm_malloc, mm_free, mm_realloc)를 trace로 검증하는 실습이다.

2. 이번 글은 segregated free list 이론을 처음부터 다시 설명하는 글이 아니라, 2편 explicit allocator 위에 크기 클래스 분기를 얹으면서 바뀐 코드와 흐름을 읽는 글이다.

핵심 관점
3편은 allocator 전체를 새로 쓰는 단계가 아니다. 2편 explicit 구조를 최대한 재사용하면서, free block이 들어가는 입구와 탐색 시작점을 크기 클래스별로 분기하는 단계다.

바뀐 핵심 아이디어를 한 줄로 말하면

2편 explicit free list가 “free block만 따로 순회한다”였다면, 3편 segregated free list는 “free block도 크기가 비슷한 것끼리 먼저 모아 둔 다음, 요청 크기에 가까운 bucket부터 찾는다”로 한 단계 더 나아간다. 그래서 3편에서 제일 중요한 함수는 find_fit 하나이고, 그 find_fit를 가능하게 만드는 전처리가 get_list_index, insert_free_block, remove_free_block다.

2편 explicit와 3편 segregated를 그림으로 보면

2편 explicit free list

free_listp

→

free A

→

free B

→

free C

free block만 순회하긴 하지만, 작은 블록과 큰 블록이 한 체인에 섞여 있다.

3편 segregated free list

index 4 부근

작은 요청

24

32

index 6 부근

중간 요청

96

128

index 9 부근

큰 요청

1024

그 이상

현재 get_list_index()는 정교한 수동 구간표가 아니라, 비트 쉬프트 기반의 거친 로그형 분류다. 그래서 이 그림은 “버킷 경계값”보다 “요청 크기에 따라 시작 index가 달라진다”는 흐름을 보여주는 용도다.

3편에서 실제로 바뀐 코드는 이 다섯 군데다

1. free list head 하나가 배열로 바뀐다

free_listp가 사라지고 seg_free_lists[LISTLIMIT]가 생긴다.

2. get_list_index()가 새로 생긴다

블록 크기를 기준으로 어느 class에 넣고 어디서부터 탐색할지 결정한다.

3. insert_free_block()과 remove_free_block()가 bucket-aware가 된다

이제 단순 연결과 해제가 아니라 “어느 리스트에서” 연결하고 제거할지까지 포함한다.

4. mm_init()이 class head 전체를 초기화한다

head 하나만 NULL로 두던 코드가 배열 초기화 루프로 바뀐다.

5. find_fit()이 “요청 크기와 가까운 class”부터 올라간다

3편의 실질적 성능 포인트는 여기 있다. 반면 place()와 coalesce()는 인터페이스를 재사용하면서 내부 의미만 달라진다.

1. free_listp 하나에서 seg_free_lists[] 배열로 넘어간다

2편 explicit allocator의 전제는 단순했다. free block이면 전부 한 연결 리스트 안에 넣고, 거기서 first-fit을 한다. 3편은 이 전제를 바꾼다. free block을 저장하는 구조는 그대로 linked list이지만, 그 linked list head가 하나가 아니라 여러 개가 된다.

2편 explicit

static void *free_listp;

3편 segregated

#define LISTLIMIT 10
static void *seg_free_lists[LISTLIMIT];

static int get_list_index(size_t size) {
    int index = 0;
    while ((index < LISTLIMIT - 1) && (size > 1)) {
        size >>= 1;
        index++;
    }
    return index;
}

이 코드가 바꾸는 흐름

2편: “free block이면 일단 한 체인에 붙인다.”

3편: “free block의 크기를 먼저 보고, 그 크기에 맞는 head를 고른 뒤 그 체인에 붙인다.”

즉 free list라는 자료구조 자체는 유지된다. 대신 list 하나를 관리하던 allocator가 이제는 “head 배열 + 각 head가 가리키는 여러 체인”을 관리해야 한다.

2. get_list_index()는 탐색 비용을 줄이기 위한 입구 선택 함수다

이 함수는 alloc/free 자체를 하진 않지만, 3편에서 가장 중요한 정책 함수다. 같은 free block 체인이라도 asize가 24인지 512인지에 따라 처음부터 같은 bucket을 뒤질 필요는 없다. 현재 구현은 비트 쉬프트를 이용해 거칠게 크기 클래스를 나눈다.

static int get_list_index(size_t size) {
    int index = 0;

    while ((index < LISTLIMIT - 1) && (size > 1)) {
        size >>= 1;
        index++;
    }
    return index;
}

이 함수를 그림으로 보면

size 24

작은 index 쪽 bucket으로 간다

size 96

중간 index에서 탐색을 시작한다

size 1024

큰 index bucket으로 간다

중요한 건 정확한 경계값보다 “요청 크기에 따라 처음 보는 free block 후보 집합이 달라진다”는 점이다. 3편의 성능 의도는 거의 이 함수 하나에 걸려 있다.

비판적으로 보면

현재 구현의 class 정책은 아주 정교한 구간 설계가 아니라 거친 로그형 분류에 가깝다. 즉 3편은 “최적의 bucket 설계”를 끝낸 버전이라기보다, explicit보다 탐색 입구를 더 잘 나눈 첫 개선판으로 읽는 게 맞다.

3. insert/remove는 이제 연결 함수가 아니라 bucket 선택까지 책임진다

2편에서 insert_free_block과 remove_free_block의 역할은 free list 하나를 LIFO 방식으로 관리하는 것이었다. 3편에서는 이 인터페이스 이름은 그대로지만, 내부 책임이 넓어진다. 이제는 “어디에 연결할지”가 아니라 “어느 리스트에 연결할지”까지 같이 결정해야 한다.

2편 explicit insert

PRED(bp) = NULL;
SUCC(bp) = free_listp;
if (free_listp != NULL)
    PRED(free_listp) = bp;
free_listp = bp;

3편 segregated insert

int index = get_list_index(GET_SIZE(HDRP(bp)));
void *head = seg_free_lists[index];

PRED(bp) = NULL;
SUCC(bp) = head;
if (head != NULL)
    PRED(head) = bp;
seg_free_lists[index] = bp;

2편 explicit remove

if (PRED(bp) != NULL)
    SUCC(PRED(bp)) = SUCC(bp);
else
    free_listp = SUCC(bp);

3편 segregated remove

int index = get_list_index(GET_SIZE(HDRP(bp)));

if (PRED(bp) != NULL)
    SUCC(PRED(bp)) = SUCC(bp);
else
    seg_free_lists[index] = SUCC(bp);

이제 free block 이동은 이렇게 읽으면 된다

1. 현재 free block의 크기를 읽는다.

2. 그 크기에 맞는 index를 계산한다.

3. 해당 bucket head에서 연결과 해제를 수행한다.

즉 3편에서 free block은 “이전/다음 free block”만 아는 게 아니라, 자기 크기 때문에 어느 list에 속해야 하는지도 사실상 같이 알고 있는 셈이다.

4. mm_init은 head 하나를 비우는 함수에서 배열 전체를 준비하는 함수가 된다

2편에서는 free list head가 하나였으니 free_listp = NULL이면 끝났다. 3편에서는 allocator가 여러 class를 동시에 관리하므로 초기화도 달라진다. 여기서 중요한 건 코드 길이가 아니라, 초기화 대상이 단일 포인터에서 여러 head 배열로 늘어난다는 점이다.

2편 explicit

free_listp = NULL;

3편 segregated

int i;
for (i = 0; i < LISTLIMIT; i++)
    seg_free_lists[i] = NULL;

이 줄이 말해주는 것

2편까지의 allocator는 “free chain 하나만 일관되게 유지하면 된다”는 구조였다. 3편부터는 “크기 클래스 여러 개의 head가 모두 일관되게 비어 있거나 채워져야 한다”는 구조로 바뀐다.

5. 진짜 성능 의도는 find_fit에서 드러난다

3편에서 가장 큰 의미를 갖는 코드는 find_fit다. 2편 explicit에서는 free block만 순회하긴 했지만, 여전히 첫 head에서 끝까지 더듬는 구조였다. 3편 segregated에서는 요청 크기와 가까운 bucket을 먼저 고르고, 거기서 맞는 블록이 없을 때만 더 큰 bucket으로 올라간다.

2편 explicit find_fit

for (bp = free_listp; bp != NULL; bp = SUCC(bp)) {
    if (asize <= GET_SIZE(HDRP(bp))) {
        return bp;
    }
}

3편 segregated find_fit

for (index = get_list_index(asize); index < LISTLIMIT; index++) {
    for (bp = seg_free_lists[index]; bp != NULL; bp = SUCC(bp)) {
        if (asize <= GET_SIZE(HDRP(bp))) {
            return bp;
        }
    }
}

실제로는 이렇게 읽으면 된다

요청 크기 asize가 들어온다.

get_list_index(asize)가 어느 bucket부터 보는 게 맞을지 결정한다.

그 bucket에서 first-fit을 하고, 없으면 더 큰 bucket으로 올라간다.

즉 3편은 first-fit을 버린 게 아니다. first-fit의 시작 구간을 더 작게 잘라서 덜 비싸게 만든 것이다.

예를 들어 mm_malloc(96)을 보면

1. 96바이트 요청은 정렬과 오버헤드를 거쳐 asize가 계산된다.

2. get_list_index(asize)가 중간 크기 bucket을 고른다.

3. 작은 free block들이 가득한 앞쪽 bucket은 아예 건너뛸 수 있다.

4. 거기서 못 찾으면 더 큰 bucket으로 올라가지만, 출발점 자체가 이미 더 낫다.

6. place와 coalesce는 크게 안 바뀐 것처럼 보이지만, 의미는 달라진다

3편의 장점 중 하나는 2편 explicit에서 만든 인터페이스를 거의 그대로 재사용한다는 점이다. place는 여전히 할당 전에 free block을 리스트에서 제거하고, split 후 남은 조각을 다시 넣는다. coalesce도 여전히 이웃 free block을 빼고 병합한 뒤 결과를 다시 넣는다. 겉으로는 큰 변화가 없어 보여도, 내부적으로는 이제 그 insert/remove가 전부 크기 클래스별 bucket을 건드린다.

place가 계속 하는 일

remove_free_block(bp);
...
insert_free_block(next_bp);

coalesce가 계속 하는 일

remove_free_block(PREV_BLKP(bp));
remove_free_block(NEXT_BLKP(bp));
...
insert_free_block(bp);

place에서 실제로 달라진 흐름

1. 현재 free block bp를 제거할 때, 2편은 단일 free list에서 뺐다.

2. 3편은 remove_free_block(bp)가 GET_SIZE(HDRP(bp))를 읽고 그 크기의 bucket에서 뺀다.

3. split 후 남는 next_bp는 원래 block과 크기가 다르기 때문에, 다시 넣을 때는 아예 다른 bucket으로 들어갈 수 있다.

즉 3편의 place는 “free block 하나를 빼고 남은 조각을 다시 넣는다”는 말은 같아도, 그 조각이 다른 class head 밑으로 재배치될 수 있다는 점에서 explicit보다 의미가 커진다.

coalesce에서 실제로 달라진 흐름

remove_free_block(PREV_BLKP(bp));
remove_free_block(NEXT_BLKP(bp));
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);
insert_free_block(bp);

1. 병합 전에는 이전 free block과 다음 free block이 각각 자기 크기에 맞는 bucket에 들어 있다.

2. 병합하면서 둘을 원래 bucket에서 제거한다.

3. 병합 결과 블록은 크기가 커졌으므로, 다시 넣을 때는 이전 두 블록과 다른 index로 들어갈 수 있다.

즉 3편의 coalesce는 단순히 헤더/풋터를 다시 쓰는 함수가 아니라, 여러 bucket에 흩어져 있던 free block을 하나의 더 큰 bucket 후보로 재분류하는 함수가 된다.

여기서 읽어야 하는 포인트

3편은 모든 함수를 다시 쓰는 개선이 아니다. 오히려 2편에서 insert/remove 인터페이스를 잘 분리해 둔 덕분에, 3편에서는 그 내부를 bucket-aware하게 바꾸는 것만으로도 place와 coalesce의 상위 흐름을 재사용할 수 있다.

7. 이 구현을 allocator 일반론으로 읽으면 안 되는 부분도 있다

3편이 명확히 나아진 건 맞지만, 이걸 “segregated free list의 최종형”처럼 읽으면 곤란하다. 현재 구현은 class 경계를 매우 거칠게 잡고 있고, bucket 안에서는 여전히 first-fit이다. 또 realloc은 여전히 단순 복사 방식이라, segregated free list로 바뀌었다고 해서 allocator 전체가 완성형이 된 건 아니다.

좋아진 점: 탐색 시작점이 요청 크기와 가까워졌다.

남은 점: class 경계 자체는 아직 조밀하지 않다.

남은 점: bucket 안에서는 best-fit이 아니라 first-fit을 그대로 쓴다.

남은 점: realloc 최적화와 heap checker는 아직 별도 과제다.

정리하면

1편 implicit이 “힙 전체를 순회하면서 allocator 문법을 익히는 단계”였다면, 2편 explicit은 “free block만 따로 모아 탐색 대상을 줄이는 단계”였다. 이번 3편 segregated는 그 explicit 구조를 버리지 않고, 그 free block 체인을 크기 클래스별로 나눠 탐색 시작점까지 개선하는 단계다. 그래서 이 글의 핵심은 복잡한 이론보다 free_listp가 seg_free_lists[]로 바뀌고, find_fit 앞에 get_list_index()가 들어오면서 allocator가 “어디부터 볼 것인가”를 더 똑똑하게 고른다는 점에 있다.

이 글을 읽고 손으로 확인해볼 질문

1. 2편 explicit와 비교했을 때 3편에서 새로 생긴 정책 함수는 무엇인가?

2. find_fit가 이제 어떤 bucket부터 탐색하는지 손으로 따라갈 수 있는가?

3. place와 coalesce는 코드가 덜 바뀌어 보여도, 왜 실제 의미는 달라졌는가?

원전 실습을 같이 보고 싶다면

Malloc Lab handout은 mm.c 하나를 제출 파일로 두고, mdriver가 trace로 동작을 검증하는 구조다. 작은 trace로 시작해 구조를 확인하려면 mdriver -V -f short1-bal.rep 같은 흐름을 같이 보는 편이 좋다.

• CS:APP Labs page
• Malloc Lab Extended Recitation