컴퓨터 시스템 : CSAPP 9장 정리 - 9.9.12 종합 설계 : 간단한 할당기의 구현 Part.1

CSAPP 9.9.12 '간단한 할당기의 구현(Putting It Together: Implementing a Simple Allocator)'

---

할당기를 만드는 것은 까다로운 작업이다. 블록 포맷, 가용 리스트 포맷, 배치 정책, 분할 정책, 통합 정책 등 다양한 선택지가 존재하기 때문이다. 또한 안전한 타입 시스템 밖에서 포인터 캐스팅과 산술 연산 같은 오류를 유발하기 쉬운 저수준 프로그래밍을 해야 하는 것도 도전 과제다.

간단한 할당기라도 코드 양은 많지 않지만, 디테일이 매우 섬세하여 실수가 용납되지 않는다. 고급 언어에 익숙한 학생들은 이 스타일의 프로그래밍을 처음 접할 때 벽에 부딪히는 경우가 많다. 이를 극복하기 위해, 묵시적 가용 리스트(implicit free list) 와 즉시 경계 태그 통합(immediate boundary-tag coalescing) 을 기반으로 한 간단한 할당기 구현 과정을 다룬다.

이 할당기는 최대 블록 크기를 2^32 = 4GB로 설정한다. 코드 또한 64비트 클린하게 작성하여 32비트(gcc -m32)와 64비트(gcc -m64) 모두에서 수정 없이 실행할 수 있다​.

---

전체 설계

할당기는 memlib.c라는 패키지를 통해 제공되는 메모리 모델을 사용한다. 이 모델을 통해 시스템 수준의 malloc과 충돌 없이 할당기를 실행할 수 있게 한다.

• mem_init() 함수는 힙을 이중 워드(double-word) 정렬된 커다란 바이트 배열로 초기화한다.
• mem_heap부터 mem_brk까지의 바이트는 현재 할당된 가상 메모리를 나타낸다.
• mem_brk 이후의 바이트는 아직 할당되지 않은 가상 메모리를 나타낸다.
• 추가 힙 메모리가 필요할 경우, mem_sbrk()를 호출해 메모리를 요청한다. 이 함수는 시스템의 sbrk와 같은 인터페이스와 의미를 갖지만, 힙을 줄이는 요청은 거부한다​.

외부로 제공하는 함수

할당기는 다음 세 가지 함수를 외부에 제공한다.

extern int mm_init(void);
extern void *mm_malloc(size_t size);
extern void mm_free(void *ptr);

• mm_init()는 할당기를 초기화한다. 성공 시 0을 반환하고 실패 시 -1을 반환한다.
• mm_malloc(size_t size)는 메모리를 할당한다.
• mm_free(void *ptr)는 메모리를 해제한다​.

---

프롤로그와 에필로그 블록

할당기는 힙(heap)의 시작과 끝에 프롤로그 블록과 에필로그 블록을 배치한다.

• 프롤로그 블록(prologue block) 은 크기가 8바이트인 할당된 블록이다. 이 블록은 빈 힙이 아닌 정상적인 블록 시퀀스가 항상 존재하게 만든다. 이를 통해 통합(coalescing) 로직을 단순하게 유지할 수 있다. 프롤로그 블록은 실제로는 헤더와 풋터만 존재하고, 내부 payload는 사용하지 않는다.
• 에필로그 블록(epilogue block) 은 크기가 0인 할당된 블록이다. 이 블록은 힙의 마지막에 위치한다. 새로운 블록이 추가될 때까지 힙의 끝을 나타내는 역할을 한다. 에필로그 블록 덕분에 힙 끝을 체크하기 위해 별도의 예외 처리를 할 필요가 없다.

구체적으로 힙을 초기화할 때 mm_init() 함수는 다음과 같은 순서로 힙을 구성한다:

1. 정렬 패딩(alignment padding) 워드를 추가한다. (8바이트 정렬 보장)
2. 프롤로그 블록을 추가한다. (8바이트, 할당 상태)
3. 에필로그 블록을 추가한다. (0바이트, 할당 상태)

---

가용 리스트 조작을 위한 기본 상수와 매크로

간단한 할당기 구현에서는 블록과 힙을 조작하기 위해 여러 상수와 매크로를 정의한다. 이들은 코드의 가독성과 효율성을 높인다.

워드와 더블 워드 크기

• WSIZE는 워드(word) 크기를 바이트 단위로 정의한다. 4바이트이다.

#define WSIZE 4

• DSIZE는 더블 워드(double word) 크기를 바이트 단위로 정의한다. 8바이트이다.

#define DSIZE 8

힙 확장 단위

• CHUNKSIZE는 초기 힙 확장 크기를 설정한다. 보통 1<<12 (4KB)로 설정하여 페이지 크기와 맞춘다.

#define CHUNKSIZE (1<<12)

이 기본 상수들은 힙을 설정하거나 메모리를 할당할 때 기본적인 단위로 사용한다.

---

기본 연산 매크로

최댓값 계산

• MAX(x, y)는 두 값 중 큰 값을 반환한다.

#define MAX(x, y) ((x) > (y) ? (x) : (y))

패킹(packing)

• PACK(size, alloc)는 크기와 할당 여부를 하나의 워드로 결합한다. 이 값은 블록의 헤더와 풋터에 저장된다.

#define PACK(size, alloc) ((size) | (alloc))

메모리 접근

• GET(p)는 포인터 p가 가리키는 워드의 값을 읽어온다.

#define GET(p) (*(unsigned int *)(p))

• PUT(p, val)은 포인터 p가 가리키는 워드에 값을 저장한다.

#define PUT(p, val) (*(unsigned int *)(p) = (val))

블록 크기와 할당 여부 추출

• GET_SIZE(p)는 포인터 p가 가리키는 헤더나 풋터로부터 블록의 크기를 추출한다. 하위 비트들을 무시하기 위해 마스크 연산을 수행한다.

#define GET_SIZE(p) (GET(p) & ~0x7)

• GET_ALLOC(p)는 포인터 p가 가리키는 헤더나 풋터로부터 블록의 할당 비트를 추출한다.

#define GET_ALLOC(p) (GET(p) & 0x1)

블록 포인터 연산

• HDRP(bp)는 블록 포인터 bp로부터 헤더 주소를 얻는다.

#define HDRP(bp) ((char *)(bp) - WSIZE)

• FTRP(bp)는 블록 포인터 bp로부터 풋터 주소를 얻는다.

#define FTRP(bp) ((char *)(bp) + GET_SIZE(HDRP(bp)) - DSIZE)

다음/이전 블록 포인터

• NEXT_BLKP(bp)는 블록 포인터 bp의 다음 블록 주소를 얻는다.

#define NEXT_BLKP(bp) ((char *)(bp) + GET_SIZE(((char *)(bp) - WSIZE)))

• PREV_BLKP(bp)는 블록 포인터 bp의 이전 블록 주소를 얻는다.

#define PREV_BLKP(bp) ((char *)(bp) - GET_SIZE(((char *)(bp) - DSIZE)))

이 상수와 매크로들을 기반으로, 블록 크기 계산, 가용 블록 탐색, 메모리 병합(coalescing) 같은 고수준 연산들을 깔끔하고 효율적으로 구현할 수 있다​.

---

초기 가용 리스트 만들기

초기 가용 리스트는 mm_init() 함수 안에서 설정한다. 할당기가 처음 초기화될 때, 힙(heap)에 최소한의 구조를 만들어 정상적인 가용 리스트 조작이 가능하도록 준비한다.

mm_init() 함수는 다음 순서로 동작한다:

1. mem_sbrk(4 * WSIZE)를 호출하여 힙 공간을 16바이트만큼 확장한다. 이 공간은 다음 네 개의 워드를 담는다.
   • 패딩 워드(8바이트 정렬을 맞추기 위한 더미 값)
   • 프롤로그 헤더 (크기 8바이트, 할당 상태)
   • 프롤로그 풋터 (크기 8바이트, 할당 상태)
   • 에필로그 헤더 (크기 0바이트, 할당 상태)
2. 각 워드에 적절한 값을 설정한다.
   • 패딩 워드는 0으로 채운다.
   • 프롤로그 블록의 헤더와 풋터는 PACK(DSIZE, 1)을 저장한다. (8바이트, 할당됨)
   • 에필로그 블록의 헤더는 PACK(0, 1)을 저장한다. (0바이트, 할당됨)
3. extend_heap(CHUNKSIZE/WSIZE)를 호출하여 초기에 사용할 가용 블록을 만든다.

int mm_init(void)
{
    /* Create the initial empty heap */
    if ((heap_listp = mem_sbrk(4*WSIZE)) == (void *)-1)
        return -1;
    PUT(heap_listp, 0); /* Alignment padding */
    PUT(heap_listp + (1*WSIZE), PACK(DSIZE, 1)); /* Prologue header */
    PUT(heap_listp + (2*WSIZE), PACK(DSIZE, 1)); /* Prologue footer */
    PUT(heap_listp + (3*WSIZE), PACK(0, 1)); /* Epilogue header */
    heap_listp += (2*WSIZE);

    /* Extend the empty heap with a free block of CHUNKSIZE bytes */
    if (extend_heap(CHUNKSIZE/WSIZE) == NULL)
        return -1;
    return 0;
}

---

extend_heap 함수

extend_heap 함수는 요청한 워드 수만큼 힙을 확장하고, 새로 생긴 공간을 하나의 큰 가용 블록으로 만든다.

extend_heap 함수의 주요 작업은 다음과 같다:

• mem_sbrk를 호출하여 메모리를 확장한다.
• 새 가용 블록의 헤더와 풋터를 설정한다. (할당 상태 = 0)
• 새 에필로그 블록을 생성한다. (크기 0, 할당 상태 = 1)
• 생성된 새 가용 블록에 대해 coalesce를 호출하여 이전 블록이 가용 상태였다면 병합한다.

static void *extend_heap(size_t words)
{
    char *bp;
    size_t size;

    /* Allocate an even number of words to maintain alignment */
    size = (words % 2) ? (words+1) * WSIZE : words * WSIZE;
    if ((long)(bp = mem_sbrk(size)) == -1)
        return NULL;

    /* Initialize free block header/footer and the epilogue header */
    PUT(HDRP(bp), PACK(size, 0)); /* Free block header */
    PUT(FTRP(bp), PACK(size, 0)); /* Free block footer */
    PUT(HDRP(NEXT_BLKP(bp)), PACK(0, 1)); /* New epilogue header */

    /* Coalesce if the previous block was free */
    return coalesce(bp);
}

---

다음 포스팅에 이어서 설명을 하겠다.