2026. 10. 1. 23:07ㆍ크래프톤 정글/포스팅
지금 위치: 네 가지 결정 중 첫 번째, 추적입니다.
나머지 세 가지(배치, 분할, 병합)가 전부 이 결정 위에서 돌아갑니다.
이번 파트의 질문: allocator는 "이 블록이 어디서 시작하고, 얼마나 크고, 쓰이는 중인지"를 어디에 어떻게 기록할까?
1. 문제: 힙은 그냥 바이트의 나열이다
힙은 구분선이 없는 연속된 바이트입니다. 그 위에서 allocator가 알아야 할 것은 이 둘입니다.
- 블록이 어디서 끝나는지 (= 크기)
- 블록이 allocated인지 free인지
그리고 제약 하나가 있습니다.
파트 2에서 봤듯이 allocator의 관리 정보자체도 힙 안에 저장해야 합니다(별도 저장 공간 불가).
그래서 이 정보를 블록 내부에 심어둡니다.
2. 해결: 헤더(header)를 붙인다
블록 맨 앞에 1워드(4바이트) 헤더를 둡니다. 블록 구성은 이렇습니다.
┌────────┬──────────────────────┬─────────────┐
│ Header │ Payload │ Padding(선택)│
│ (4B) │ (애플리케이션이 쓰는 곳) │ │
└────────┴──────────────────────┴─────────────┘
↑
malloc이 돌려주는 포인터 = payload의 시작- Header: 블록 크기 + 할당 여부(allocated)
- Payload: 애플리케이션이 요청한 데이터가 들어가는 곳
- Padding: 정렬이나 기타 이유로 붙는 빈 공간 (없을 수도 있음)
중요한 점 두 가지
- 블록 크기는 헤더와 패딩을 모두 포함합니다. 즉 블록 크기 = 헤더 + payload + 패딩입니다.
- malloc이 돌려주는 포인터는 블록의 시작이 아니라 payload의 시작입니다. 그래서 헤더는 포인터에서 4바이트 앞에 있습니다.
헤더가 payload 앞에 있어서 free(p)는 p만 받고도 헤더를 읽어 블록 크기를 알 수 있습니다. 그래서 free는 크기를 인자로 받지 않아도 됩니다.
3. 헤더 한 워드에 두 정보를 넣는 법
헤더는 32비트 한 워드이고, 여기에 크기와 할당 여부를 같이 담습니다. 비결은 정렬 규칙입니다.
블록 크기는 항상 8의 배수라서 이진수로 쓰면 하위 3비트가 항상 0입니다.
24 = 0000 0000 0000 0000 0000 0000 0001 1000
---
└─ 하위 3비트는 000항상 0이라면 그 자리를 다른 용도로 쓸 수 있습니다. 따라서 최하위 비트(비트 0)를 allocated 비트로 씁니다.
단, 크기를 읽을 때는 오른쪽 3칸을 0으로 바꿔서 읽을 뿐 칸을 잘라내지 않는다. 그래서 0010 0000은 크기 32이다.
31 3 2 1 0
┌──────────────────────────────┬──┬──┬──┐
│ 블록 크기를 나타내는 숫자 │ 0│ 0│ a│
└──────────────────────────────┴──┴──┴──┘
a = 1: allocated
a = 0: free최하위 비트만 바꾸는 연산 OR - PACK(size, alloc)
컴퓨터(코드)는 "맨 오른쪽 비트만 바꿔"라는 명령을 따로 갖고 있지 않습니다. 숫자를 통째로 만들어서 저장해야 합니다. 그래서 "24에서 맨 오른쪽 비트만 1로 만든 숫자"를 만드는 방법이 필요하고, 그걸 해주는 연산이 OR입니다.
예시: PACK(24, 1): 크기 24, allocated인 헤더 만들기
0001 1000 ← 크기 24
| 0000 0001 ← allocated를 뜻하는 값 (맨 오른쪽 칸만 1)
-----------
0001 1001 ← OR 연산 결과 (최종 헤더값)
예시: PACK(40, 0): 크기 40, free인 헤더 만들기
0010 1000 ← 크기 40
| 0000 0000 ← free를 뜻하는 값 (전부 0)
-----------
0010 1000 ← OR 연산 결과 (최종 헤더값)
헤더에서 값 꺼낼 때 연산 AND - GET_SIZE(p), GET_ALLOC(p)
헤더 예시: 0001 1001
1) 크기 꺼내기: GET_SIZE(p)
맨 오른쪽 3칸만 지우고 나머지는 남기는 마스크를 사용해 AND 연산을 합니다.
0001 1001 ← p가 가리키는 헤더값
& 1111 1000 ← 맨 오른쪽 3칸을 지우고 나머지만 남기도록 하는 마스크
-----------
0001 1000 ← 결과 = 크기를 의미하는 24만 남음AND는 둘 다 1일 때만 1이므로, 아래 줄이 0인 칸은 전부 0이 되고, 아래 줄이 1인 칸(왼쪽 5칸)만 헤더의 값이 그대로 살아남습니다. 그래서 크기만 남습니다.
2) 상태 꺼내기: GET_ALLOC(p)
맨 오른쪽 칸만 남기고 나머지를 0으로 만드는 AND 연산
0001 1001 ← p가 가리키는 헤더값
& 0000 0001 ← 맨 오른쪽 칸만 남기는 마스크
-----------
0000 0001 ← 결과 = 1 → allocated를 의미하는 비트만 남음
4. 이 구조가 만드는 것: implicit free list
헤더에 블록의 크기가 있으므로 헤더 → 다음 헤더로 건너뛸 수 있습니다.
참고로 allocator는 블록을 항상 payload 주소(bp)로 가리키고, 헤더는 bp - 4로 찾고, 다음 블록은 bp + 해당 헤더크기로 건너뜁니다.
[H|payload|pad][H|payload|pad][H|...][H|...] [끝: 크기 0, allocated]
↑ 크기만큼 건너뜀 ↑ 크기만큼 건너뜀현재 블록 시작 + 현재 블록 크기 = 다음 블록 시작이므로, 힙의 첫 블록부터 끝까지 블록을 차례로 훑을 수 있습니다. 이렇게 별도의 포인터 연결 없이 크기 필드가 암묵적으로(implicitly) 빈 블록들을 이어주기 때문에 implicit free list라고 부릅니다.
- 장점: 단순하다
- 단점: 빈 블록을 찾으려면 힙 전체를 훑어야 해서, 비용이 전체 블록 수(할당 + 빈 블록)에 비례한다
훑기를 멈추려면 끝을 알려주는 표식이 필요해서, 책은 크기 0, allocated 비트 1인 특별한 끝 블록(epilogue)을 둡니다.
5. 최소 블록 크기 (내부 단편화와 연결)
정렬(8바이트)과 블록 형식이 만나면 블록이 작아질 수 있는 한계가 생깁니다.
- 헤더만 4바이트이고, 블록 크기는 8의 배수여야 합니다.
- 헤더만 있는 블록(4B)은 8의 배수가 아니므로 최소 블록의 크기는 8바이트(2워드)입니다: 헤더 1워드 + 1워드(payload/패딩).
- 단 설계에 따라 최소 크기는 달라집니다.
그래서 애플리케이션이 malloc(1)을 해도 allocator는 최소 크기 블록을 만들고, 그 차이가 내부 단편화를 만드는 원인 중 하나입니다.
힙은 구분선 없는 바이트 덩어리이므로, allocator는 각 블록 맨 앞에 1워드 헤더를 두고 블록 크기와 할당 여부를 기록한다. 블록 크기는 항상 8의 배수라 하위 3비트가 0이므로, 그 중 최하위 비트를 allocated 비트로 쓴다(PACK: 크기 OR 비트). malloc이 돌려주는 포인터는 payload 시작이고 헤더는 그 4바이트 앞에 있다. 헤더의 크기 필드로 다음 블록을 건너뛰며 힙 전체를 훑을 수 있어 implicit free list라 부른다. 최소 블록 크기가 있어 작은 요청도 내부 단편화가 생긴다.