Heap Bin 정리
1. Tcache (Per-Thread Cache)
도입: glibc 2.26
목적: 멀티스레드 환경에서 락 없이 초고속 할당
구조:
스레드마다 독립적으로 존재:
스레드 1의 Tcache:
빈 #1 (24B) : [24B]→[24B]→[24B]→NULL (3/7)
빈 #2 (32B) : [32B]→NULL (1/7)
빈 #3 (40B) : NULL (0/7)
...
빈 #64 (1032B): [1032B]→[1032B]→NULL (2/7)
스레드 2의 Tcache:
빈 #1 (24B) : [24B]→NULL (1/7)
... 완전히 별개로 존재
free() 시:
Tcache 범위(24~1032B)이고 해당 빈이 7개 미만
→ 그냥 단일 연결 리스트 맨 앞에 추가 (LIFO)
→ 병합 ❌, P비트 변경 ❌, 락 ❌
→ 매우 빠름
malloc() 시:
해당 크기 빈에 청크 있으면
→ 단일 연결 리스트 맨 앞에서 꺼냄 (LIFO)
→ 락 없이 즉시 반환
한계:
빈당 최대 7개 제한
→ 7개 초과 시 이후 free()는 패스트 빈/언소티드 빈으로
크기 범위 초과 (>1032B)
→ Tcache 사용 불가
2. 패스트 빈 (Fast Bin)
목적: 작은 청크의 빠른 재사용 (Tcache 도입 전 주력 캐시)
구조:
10개의 빈, 각각 하나의 크기만 담당:
패스트 빈 #1 (16B) : [16B]→[16B]→NULL
패스트 빈 #2 (24B) : [24B]→NULL
패스트 빈 #3 (32B) : [32B]→[32B]→[32B]→NULL
패스트 빈 #4 (40B) : NULL
패스트 빈 #5 (48B) : [48B]→NULL
패스트 빈 #6 (56B) : NULL
패스트 빈 #7 (64B) : [64B]→[64B]→NULL
패스트 빈 #8 (72B) : NULL
패스트 빈 #9 (80B) : NULL
패스트 빈 #10 (88B) : [88B]→NULL
free() 시:
크기 ≤ 88B
→ 해당 빈 맨 앞에 추가 (LIFO)
→ 병합 ❌
→ P비트 변경 ❌ (인접 청크에게 "나 아직 살아있음"처럼 보임)
→ 모든 스레드 공유이므로 락 🔒 필요
malloc() 시:
해당 크기 빈에 청크 있으면
→ 맨 앞에서 꺼냄 (LIFO)
→ 즉시 반환
Consolidation (주기적 정리):
발생 조건:
├── malloc(>512B) 요청 시 (64비트: >1024B)
├── free(>64KB 청크) 시
└── malloc_trim() / mallopt() 호출 시
발생 시 동작:
패스트 빈의 모든 청크
→ P비트 "진짜로" 0으로 설정
→ 인접 청크와 병합
→ 언소티드 빈으로 이동
3. 언소티드 빈 (Unsorted Bin)
목적: 지연 정렬(lazy sorting)로 free/malloc 오버헤드 감소
스몰/라지 빈 입장 전 임시 창고
구조:
단 1개의 빈, 크기 무관, 순서 없음:
[빈 헤드] ◀──▶ [512B] ◀──▶ [32B] ◀──▶ [256B] ◀──▶ [빈 헤드]
뒤죽박죽, 크기/순서 무관
free() 시:
크기 > 88B (또는 Tcache 가득 찬 경우)
→ 인접 청크 병합 먼저 수행
├── 앞 청크 P비트 = 0? → 앞 청크와 병합
└── 뒷 청크 P비트 = 0? → 뒷 청크와 병합
→ 병합된 청크를 빈 헤드 바로 뒤에 삽입 (이중 연결)
→ 락 🔒 필요
malloc() 시:
언소티드 빈을 처음부터 끝까지 순회:
├── 요청 크기와 정확히 일치 → 즉시 반환 ✅
├── 요청보다 크면 → 분할(split)
│ 요청 크기만큼 반환 ✅
│ 남은 조각 → 다시 언소티드 빈으로
└── 맞지 않으면 → 크기에 따라 스몰/라지 빈으로 분류
다음 항목으로 계속 순회
4. 스몰 빈 (Small Bin)
목적: 중소형 고정 크기 청크의 정렬 보관
구조:
62개의 빈, 각각 하나의 크기만 담당 (16B 단위 증가):
스몰 빈 #1 (16B) : [16B] ◀──▶ [16B] ◀──▶ NULL
스몰 빈 #2 (24B) : [24B] ◀──▶ NULL
스몰 빈 #3 (32B) : [32B] ◀──▶ [32B] ◀──▶ [32B] ◀──▶ NULL
...
스몰 빈 #62 (1016B): [1016B] ◀──▶ NULL
free() 시:
직접 입장 ❌
언소티드 빈에서 malloc() 탐색 중 분류되어 입장
→ 빈 헤드 뒤에 삽입
→ 병합 ✅ (인접 free 청크와)
→ 이중 연결 리스트
→ 락 🔒 필요
malloc() 시:
요청 크기에 해당하는 빈 확인
→ 빈 헤드 바로 앞(꼬리)에서 꺼냄 (FIFO)
→ 즉시 반환 ✅
→ 고정 크기이므로 분할 불필요
5. 라지 빈 (Large Bin)
목적: 대형 가변 크기 청크의 정렬 보관
구조:
63개의 빈, 각각 크기 범위를 담당:
라지 빈 #1 (1024~1088B) : 크기 내림차순 정렬
라지 빈 #2 (1088~1152B) : 크기 내림차순 정렬
라지 빈 #3 (1152~1216B) : 크기 내림차순 정렬
...
각 빈 내부는 크기 내림차순 정렬:
[2048B] ◀──▶ [1800B] ◀──▶ [1500B] ◀──▶ [1100B]
↑ 가장 큼 ↑ 가장 작음
free() 시:
직접 입장 ❌
언소티드 빈에서 malloc() 탐색 중 분류되어 입장
→ 크기 내림차순 위치에 삽입 (정렬 유지)
→ 병합 ✅
→ 이중 연결 리스트
→ 락 🔒 필요
malloc() 시:
요청 크기 이상의 가장 작은 청크 탐색 (best-fit)
→ 청크 분할(split)
요청 크기만큼 반환 ✅
남은 조각 → 언소티드 빈으로
전체 비교 총정리
크기 기준:
16B 24B 88B 1024B
│ │ │ │
▼ ▼ ▼ ▼
┌──────┬───────────┬───────────────┬──────────────┐
│패스트 │ Tcache │ 스몰 빈 │ 라지 빈 │
│ │ + 스몰빈 │ │ │
└──────┴───────────┴───────────────┴──────────────┘
↑
언소티드 빈은 크기 무관 (임시 창고)
속도 기준 (빠른 순):
⚡⚡⚡ Tcache 락 없음, 내 전용
⚡⚡ 패스트 빈 락 있음, 병합 없음
⚡ 언소티드 락 있음, 순회 필요
⚡ 스몰 빈 락 있음, 정렬됨
⚡ 라지 빈 락 있음, 정렬+분할
🐢 OS 요청 힙 확장
free() / malloc() 최종 흐름
━━━━━━━━━━━━━━━━ free(ptr) ━━━━━━━━━━━━━━━━
24~1032B & 빈<7개
│YES
▼
[Tcache] ✅ 끝
│NO (범위 초과 or 가득 참)
▼
≤ 88B?
YES│ │NO
▼ ▼
[패스트] [병합 후 언소티드] ✅ 끝
✅ 끝
━━━━━━━━━━━━━━━━ malloc(size) ━━━━━━━━━━━━━━━━
① Tcache ──────────────── 있으면 반환 ✅
│없음
② 패스트 빈 (≤88B) ────── 있으면 반환 ✅
│없음
③ Consolidation 여부 확인
│
④ 언소티드 빈 순회
├── 맞으면 반환 ✅
└── 틀리면 스몰/라지로 분류
│소진
⑤ 스몰 빈 (<1024B) ────── 있으면 반환 ✅
│없음
⑥ 라지 빈 ─────────────── 있으면 분할 후 반환 ✅
│없음
⑦ OS 힙 확장 ──────────── 반환 ✅