mm.c를 교재처럼 읽기현재 allocator 코드가 힙을 어떤 규칙으로 읽고 갱신하는지를 함수 단위로 해설하는 공부 글이다.
왜 allocator는 함수 셋보다 메모리 규칙 묶음처럼 읽어야 하는가
지금 구현한 allocator는 implicit free list 기반의 비교적 단순한 구조다. 하지만 이 코드만 제대로 읽어도 힙 경계, 블록 레이아웃, 포인터 산술, free 이후 병합, realloc의 비용 같은 시스템 개념이 한 번에 연결된다. 그래서 이 글은 내 코드가 무엇을 하고 있는지를 따라가면서, allocator를 시스템 구조로 이해하는 데 초점을 둔다.
malloc lab은 “메모리를 달라 하면 주고, 돌려주면 다시 합치고, 재할당도 처리하는 작은 동적 메모리 할당기”를 직접 만드는 과제다. 드라이버는 우리가 작성한 mm.c를 호출하면서 mm_init, mm_malloc, mm_free, mm_realloc가 제대로 동작하는지 검사한다. 즉 이 글에서 보는 코드는 독립적인 유틸 함수 모음이 아니라, malloc 패키지의 핵심 함수 자리에 들어가는 제출 코드다.
mdrivermm.cmemlibmm.c 하나이고, mdriver가 trace file을 흘려 보내면서 동작을 검증한다. 보통은 short1-bal.rep, short2-bal.rep 같은 작은 trace부터 시작해서 블록 배치와 병합이 맞는지 확인한 뒤, 기본 trace 묶음으로 넘어간다.| 함수 | 과제에서 맡는 역할 | 이 글에서 보는 포인트 |
|---|---|---|
mm_init |
힙의 시작 상태를 만든다 | 프롤로그, 에필로그, 첫 free block이 왜 필요한지 |
mm_malloc |
요청 크기를 받아 블록을 할당한다 | 사용자 요청이 내부 블록 크기로 어떻게 번역되는지 |
mm_free |
할당 블록을 다시 free block으로 돌린다 | header/footer를 free로 바꾼 뒤 왜 곧바로 병합하는지 |
mm_realloc |
블록 크기를 다시 조정한다 | 현재 구현이 어디까지 단순화돼 있고 어디가 검토 포인트인지 |
이 글은 파일 전체를 한꺼번에 해설하는 대신, allocator를 이해하는 데 가장 중요한 함수 경로를 따라간다. 그래서 매크로 -> 초기화 -> malloc -> free/coalesce -> realloc 순서로 읽는다.
mm_init와 extend_heap가 힙 경계를 어떻게 세우는지mm_malloc, find_fit, place가 실제 할당을 어떻게 구성하는지mm_free, coalesce, mm_realloc가 왜 allocator의 핵심 학습 포인트인지먼저 짚고 갈 용어
이 코드가 택한 allocator 모델
지금 구현은 explicit free list나 segregated free list가 아니라, implicit free list + boundary tag + first-fit + split + coalesce 조합으로 되어 있다. 이 선택은 성능 최적화보다는 구조 이해를 우선한 셈이다. free block을 따로 체인으로 연결하지 않으므로, allocator가 힙을 어떻게 훑고 블록을 어떻게 다시 해석하는지가 더 직접적으로 보인다.
매크로가 사실상 allocator의 언어다
이 파일에서 가장 중요한 코드는 함수보다 먼저 매크로다. PACK, GET, PUT, GET_SIZE, GET_ALLOC, HDRP, FTRP, NEXT_BLKP, PREV_BLKP는 allocator 전체가 공통으로 쓰는 문법이다. 나중에 함수가 아무리 길어져도 결국은 “이 주소의 헤더를 읽고, 그 크기만큼 이동하고, 할당 비트를 바꾸는 일”을 반복한다.
size | alloc이 들어가고, payload 포인터인 bp를 기준으로 앞뒤 메타데이터 위치를 다시 계산한다.#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)) - DSIZE)
#define NEXT_BLKP(bp) ((char *)(bp) + GET_SIZE(((char *)(bp) - WSIZE)))
#define PREV_BLKP(bp) ((char *)(bp) - GET_SIZE(((char *)(bp) - DSIZE)))bpHDRP(bp)bpFTRP(bp)size|alloc 정보를 읽어서 현재 블록의 앞뒤 경계를 다시 찾아간다.예를 들어 HDRP(bp)는 payload 시작 위치에서 4바이트 뒤로 가 헤더를 읽는다. NEXT_BLKP(bp)는 현재 블록 헤더의 size를 읽어서 그만큼 앞으로 이동한다. 즉 allocator는 포인터를 무작정 더하고 빼는 코드가 아니라, 메모리 안에 저장해둔 size와 alloc 비트를 해석하면서 움직이는 코드다.
mm_init과 extend_heap은 힙의 경계를 세우는 함수다
초기화는 “메모리를 조금 확보한다”는 수준에서 끝나지 않는다. 현재 구현은 먼저 정렬 패딩, 프롤로그 헤더/풋터, 에필로그 헤더를 만들고, 그 다음 extend_heap으로 첫 free block을 추가한다. 이 구조가 있어야 힙의 시작과 끝을 예외 없이 다룰 수 있다.
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);
if (extend_heap(CHUNKSIZE / WSIZE) == NULL)
return -1;header/footer
extend_heap 후
힙 시작점의 alignment를 맞춘다.
항상 할당된 작은 블록처럼 둬서 앞쪽 경계를 안전하게 만든다.
크기 0의 가짜 블록으로 두어 순회의 종료점을 만든다.
extend_heap도 같은 이유로 중요하다. 새 free block의 헤더/풋터를 쓰고, 바로 뒤에 새 에필로그를 다시 세운다. 즉 힙 확장은 메모리를 길게 만드는 작업이 아니라, 확장된 영역을 allocator의 블록 문법 안으로 편입시키는 작업이다.
malloc 경로를 코드 그대로 따라가 보기
현재 mm_malloc의 흐름은 네 단계다. 요청 크기를 조정하고, 적당한 free block을 찾고, 배치하고, 없으면 힙을 늘린다. 여기서 중요한 건 “요청 크기”와 “실제 블록 크기”를 구분해 보는 것이다.
if (size == 0)
return NULL;
if (size <= DSIZE)
asize = 2 * DSIZE;
else
asize = DSIZE * ((size + (DSIZE) + (DSIZE - 1)) / DSIZE);
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);mm_malloc(24)를 요청하면사용자가 원하는 payload는 24바이트다.
헤더/풋터와 alignment를 감안하면
asize = 32가 된다.first-fit으로 32바이트 이상인 free block을 찾는다.
예를 들어 4096바이트 free block을 찾았다면, 앞 32바이트는 할당 블록으로 쓰고 나머지 4064바이트는 다시 free block으로 남긴다.
| 시점 | 블록 상태 | 여기서 읽어야 하는 것 |
|---|---|---|
| 할당 전 | [4096/0] |
힙 안의 큰 free block 하나가 allocator의 출발점이다. |
| 앞부분 배치 후 | [32/1] |
24바이트 요청이 내부적으로는 32바이트 블록 하나로 번역된다. |
| 남은 조각 | [4064/0] |
남은 공간도 그냥 찌꺼기가 아니라, 다음 find_fit이 다시 읽을 free block으로 남는다. |
여기서 allocator 공부의 핵심이 드러난다. 사용자는 “24바이트”를 원했지만, allocator는 그 요청을 32바이트짜리 블록 하나로 변환해 받아들인다. 즉 allocator는 raw bytes를 직접 다루는 함수가 아니라, 사용자 요청을 내부 블록 단위로 번역하는 함수에 가깝다.
find_fit과 place는 왜 항상 같이 봐야 하는가
find_fit은 free block을 찾고, place는 찾은 block을 실제로 나누어 쓰는 함수다. 이 둘은 따로 보면 단순하지만, allocator 관점에서는 사실 한 세트다. “어디를 선택할 것인가”와 “선택한 공간을 어떤 모양으로 다시 쓸 것인가”가 같이 정해져야 하기 때문이다.
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;
}
}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));
}csizeasizecsize-asize| 함수 | 하는 일 | 이 코드가 보여주는 감각 |
|---|---|---|
find_fit |
free block을 찾는다 | implicit free list에서는 탐색이 힙 순회와 같다 |
place |
선택한 block을 할당하고 필요하면 split한다 | 남는 조각도 allocator가 계속 관리해야 할 블록이다 |
여기서 자주 헷갈리는 지점은 split 조건이다. 남는 공간이 너무 작으면 새 free block으로 남겨도 의미가 없다. 그래서 현재 구현은 (csize - asize) >= 2 * DSIZE일 때만 분할한다. 즉 allocator는 모든 여유 공간을 잘게 쪼개는 게 아니라, 다시 유효한 블록이 될 수 있는 조각만 남긴다.
free와 coalesce는 메모리를 다시 시스템 안으로 돌려놓는 과정이다
mm_free는 짧지만 allocator 공부에서는 가장 중요한 함수 중 하나다. 메모리를 “없앰”이 아니라, 다음 할당에서 다시 해석 가능한 free block으로 복원하는 역할을 하기 때문이다. 헤더/풋터를 free로 바꾸고, 바로 coalesce로 넘긴다.
size_t size = GET_SIZE(HDRP(bp));
PUT(HDRP(bp), PACK(size, 0));
PUT(FTRP(bp), PACK(size, 0));
coalesce(bp);coalesce는 앞뒤 블록 상태를 읽고 네 케이스로 나눈다. 이 부분이 boundary tag의 진짜 용도를 보여 준다. 이전 블록의 상태를 알아야 하는데, 그걸 위해 현재 블록 바로 앞의 메모리에서 이전 블록의 풋터를 읽는다.
앞뒤 모두 할당 상태. 병합할 필요가 없다.
다음 블록만 free. 현재 블록을 뒤로 확장한다.
이전 블록만 free. 앞 블록으로 병합한 뒤 포인터를 옮긴다.
앞뒤 모두 free. 세 블록을 하나로 합친다.
[64/0][32/0][48/1][96/0][48/1]bp = PREV_BLKP(bp)처럼 포인터 기준도 같이 옮겨야 한다.bp만 있을 때, 이전 블록 헤더가 정확히 어디 있는지 바로 알 수는 없다.현재 realloc 구현은 단순하지만, 그대로 미화하면 안 된다
mm_realloc은 새 블록을 할당하고, 기존 데이터를 복사한 뒤, old block을 free하는 구조다. 큰 흐름만 보면 allocator 규칙을 재사용하는 단순한 구현이다. 다만 이 섹션은 “정리 잘 된 realloc”을 칭찬하는 부분이 아니라, 현재 구현이 어디까지는 분명하고 어디부터는 다시 검토해야 하는지를 읽는 부분이어야 한다.
newptr = mm_malloc(size);
if (newptr == NULL)
return NULL;
copySize = GET_SIZE(HDRP(oldptr)) - WSIZE;
if (size < copySize)
copySize = size;
memcpy(newptr, oldptr, copySize);
mm_free(oldptr);copySize = GET_SIZE(HDRP(oldptr)) - WSIZE;는 “현재 구현이 이렇게 쓰고 있다”는 사실이지, 바로 옳은 payload 계산식이라고 미화할 부분은 아니다. 블록 크기에는 헤더와 풋터가 함께 들어가므로, 이 줄은 footer 영역까지 걸칠 수 있는지 다시 점검해야 한다. 즉 이 코드는 realloc의 큰 경로는 보여주지만, 복사 길이 계산은 재검토 대상으로 읽는 편이 정확하다.그래서 이 섹션에서 가져가야 할 교훈은 “realloc도 메타데이터를 읽는다” 정도이지, 현재 구현의 세부 식이 이미 잘 정리됐다고 받아들이는 것은 아니다. 교재형으로 읽는다면 오히려 이런 줄에서 멈춰서 어디가 일반 원리이고 어디가 현재 코드의 검토 포인트인지를 구분해야 한다.
이 구현으로부터 바로 읽히는 한계
| 현재 선택 | 지금 단계의 장점 | 다음 단계에서 개선할 지점 |
|---|---|---|
| Implicit free list | 구조가 직관적이고 설명하기 쉽다 | 탐색 비용을 줄이려면 explicit free list나 segregated list가 필요하다 |
| First fit | 구현이 단순하고 trace 추적이 쉽다 | fragmentation과 배치 품질을 더 고민해야 한다 |
| 즉시 coalesce | free 직후 구조가 정리돼 이해하기 쉽다 | trace에 따라 지연 병합 전략과 비교해볼 수 있다 |
| Naive realloc | allocator 전체 규칙을 재사용한다 | 인접 free block을 이용한 제자리 확장 최적화가 없다 |
즉 지금 코드는 “좋은 allocator의 최종형”보다는, 현재 구현의 정책과 allocator 일반 원리를 분리해서 읽는 기준점에 더 가깝다. 성능 개선은 그 다음 문제고, 지금 단계의 핵심은 힙과 블록을 손으로 설명할 수 있게 되는 것이다.
직접 해볼 실습
malloc(24)를 손으로 추적해 보기- 요청 크기 24바이트를 내부 블록 크기
asize로 바꾼다. - 현재 free block 하나를 가정하고 first-fit이 어디를 잡을지 표시한다.
place이후 헤더/풋터가 어떻게 바뀌는지 적는다.- 남은 블록이 split될 조건을 같이 써 본다.
사용자 요청 24바이트가 왜 내부에서는 32바이트 블록이 되는지 설명할 수 있어야 한다.
- 앞 allocated / 뒤 allocated
- 앞 allocated / 뒤 free
- 앞 free / 뒤 allocated
- 앞 free / 뒤 free
왜 이전 블록 병합에는 풋터가 필요하고, 다음 블록 병합에는 헤더가 바로 쓰이는지 말로 설명해 본다.
- allocator를 읽을 때는 함수 이름보다 블록 규칙부터 봐야 한다.
- 헤더/풋터와 boundary tag는 free block 병합을 가능하게 만드는 핵심 장치다.
mm_malloc은 사용자 요청을 내부 블록 크기로 번역하는 함수다.find_fit와place는 탐색과 배치를 같이 설명해야 의미가 선명해진다.mm_realloc도 결국은 블록 메타데이터를 다시 읽는 함수다.
이 글은 현재 구현을 교재처럼 푼 버전이지만, malloc lab 자체를 같이 보고 읽으면 맥락이 더 잘 잡힌다. 특히 과제 구조, trace 기반 평가, 더 나아간 explicit list나 성능 해석은 원전 자료를 같이 보는 편이 좋다.
- CS:APP Labs page : malloc lab이 포함된 공식 lab 안내 페이지
- Malloc Lab Extended Recitation : implicit list, explicit list, heap checker, 성능 포인트를 더 길게 설명한 공개 자료
지금 mm.c는 빠른 allocator라기보다, 힙과 블록을 어떤 규칙으로 읽어야 하는지 몸으로 익히게 해 주는 작은 시스템 교재에 가깝다.
'크래프톤 정글 > 정글에서 문제풀기' 카테고리의 다른 글
| Malloc Lab 구현기 3편 - explicit free list에서 segregated free list로 바꾸며 달라진 것 (0) | 2026.04.14 |
|---|---|
| Malloc Lab 구현기 2편 - explicit free list 전환과 코드 흐름의 변화 (0) | 2026.04.14 |
| 이진 탐색 트리 Q5. 두 개의 스택으로 후위 순회하기 (0) | 2026.04.09 |
| 이진 탐색 트리 Q4. 한 개의 스택으로 후위 순회하기 (0) | 2026.04.09 |
| 이진 탐색 트리 Q3. 반복문으로 전위 순회하기 (0) | 2026.04.09 |