동적 메모리 할당(Malloc) 심화 및 구현 1-2

상황 설명: 묵시적 가용 리스트에서 명시적 가용 리스트로 전환하며 겪은 문제들

묵시적 가용 리스트(implicit free list)에서 명시적 가용 리스트(explicit free list) 방식으로 전환하는 과정에서, 계속해서 "힙 범위를 벗어났습니다", "세그멘테이션 폴트", 또는 "무한 루프"와 같은 에러가 발생했습니다.

특히 free list에서 SUCC(bp) 포인터가 푸터(Footer)나 다음 블록의 헤더(Header)를 침범하게 되어 잘못된 경로를 따라가거나 자기 자신을 참조하는 등의 문제가 발생했고, 이로 인해 insert_free_block()이나 find_fit() 함수가 free list를 순회하다 무한 루프에 빠지거나 프로그램이 강제 종료되곤 했습니다.

여러 차례 코드를 수정하고 구조를 바꾸던 중, 문제의 핵심은 SUCC 포인터의 offset 계산이 잘못되어 있었던 것이라는 사실을 알게 되었습니다. DSIZE(16바이트)를 더해 포인터를 참조하는 바람에 free block 내부가 아닌 외부 메모리를 침범하게 된 것입니다.

결국 SUCC(bp)의 offset을 DSIZE → WSIZE (8바이트)로 수정하고, block 내부 레이아웃 구조를 명확하게 정의한 후에야 정상 동작 + 성능 확보를 모두 만족하는 malloc 구현을 완성할 수 있었습니다.

이 글은 그 과정에서 겪었던 시행착오와 오류, 그리고 최종적으로 문제를 해결한 구조를 정리한 내용입니다.

 

 올바른 free block 레이아웃 구조

정상적으로 동작한 두 번째 코드에서는 free block의 내부 구조가 다음과 같은 포맷을 따라요:

| Header (8 byte) |
| PRED   (8 byte) |  ← 이전 free 블록 포인터
| SUCC   (8 byte) |  ← 다음 free 블록 포인터
| Payload (optional) |
| Footer (8 byte) |

이 구조는 free block 내부에서 포인터를 안전하게 읽고 쓰게 해줍니다. 비고가 되는 포인터 SUCC의 위치는 계속 잘못 설정되면 무한 루프가 발생할 수 있어요.

 

 “#define SUCC(bp) (*(void **)((char *)(bp) + DSIZE))” 의 문제

첫 번째 코드에서 리포팅의 결정적 문제가 된 번호는 다음과 같습니다:

#define WSIZE 8
#define DSIZE 16
#define SUCC(bp) (*(void **)((char *)(bp) + DSIZE)) // ❌ 잘못된 위치

해당 정의는 payload 시작점에서 복잡하게 16바이트 종료 위치를 가는데, 이것은 많은 경우 Footer 또는 다음 Header를 흡단할 수 있어 무한 루프를 생성하거나, 자기 자신을 가리키는 잘못된 경로가 되며 테스트가 중반에 정지되지 않는 문제가 발생했습니다.

 

해결: WSIZE로 간격 감소

이 문제는 SUCC(bp)의 offset을 DSIZE (16) 가 아닌, WSIZE (8)로 변경함으로써 해결되었습니다.

// ✔️ 정상 정의:
#define SUCC(bp) (*(void **)((char *)(bp) + WSIZE))

그런시간 PRED과 SUCC 포인터가 새로 생겼는 payload 가용 구간의 구조와 정확히 맞아지고, Header/Fooer과 거듭치는 문제가 더 이상 발생하지 않게 됩니다.

 

결론

말록 구조와 포인터 offset이 정확해야 malloc/free 구현은 안전하게 동작할 수 있습니다. 이번 디버그 결과를 통해 free list 구조가 잘못되면 무한 루프가 발생할 수 있고, 디버그가 어렵다는 것을 가졌습니다.

결국적으로 WSIZE 간격을 구조에 다시 적용하게 되면, 이와 같은 무한 루프 문제는 더 이상 발생하지 않고 정상적으로 구동했습니다.

 묵시적 vs 명시적 가용 리스트 구조 비교

항목	묵시적 가용 리스트 (Implicit)	명시적 가용 리스트 (Explicit)
메타데이터 구성	Header + Footer	Header + PRED + SUCC + Footer
포인터 저장 여부	❌ 없음 (순차 탐색)	✅ 있음 (PRED, SUCC)
포인터 크기	없음	8바이트 (64bit 시스템 기준)
정렬 기준	8바이트 단위 (Double Word)	8바이트 단위 (Double Word)
최소 블록 크기	8바이트 (4B + 0B + 4B)	24바이트 이상
Payload 접근 방식	Header 바로 뒤	SUCC 뒤 (PRED + SUCC 지나고)
블록 순회 방식	bp + GET_SIZE(HDRP(bp))	SUCC(bp) 따라 이동
장점	간단, 구현 쉬움	탐색 빠름, best-fit 가능
단점	탐색 느림, split 비효율	복잡, 포인터 오류시 무한루프

 

전체 코드

깃허브 주소 : https://github.com/applepc24/malloc