[Malloc Lab-2] CSAPP 9.9 동적 메모리 할당 (12) : 간단한 할당기의 구현

은채·2025년 4월 28일
CSAPPmalloc lab

Malloc Lab

목록 보기
14/21
post-thumbnail

CSAPP 책은 쌩으로 읽는다면 이해하기 매우 어렵습니다.
따라서 소단원만 그대로 따라가되, 내용을 이해하기 쉽게 재구성했습니다.

Malloc Lab을 구현할 때, 12장의 내용만으로 부족할 수 있습니다.
변수, 매크로, 함수들은 여기에 따로 정리해 두었습니다.

9.9.12 종합 설계: 간단한 할당기의 구현

할당기를 만드는 것은 결코 쉬운 작업이 아니다.
디자인 단계부터 다양한 선택지들을 고려해야 한다.

  • 블록을 어떻게 구성할지 (Block Format)
  • free list를 어떻게 관리할지 (Free List Format)
  • 메모리를 어디에 배치할지 (Placement Policy)
  • 요청한 크기만큼 어떻게 블록을 쪼갤지 (Splitting Policy)
  • 가용 블록들을 어떻게 연결할지 (Coalescing Policy)

각각의 선택이 성능과 안정성에 직접적인 영향을 미치기 때문에, 설계 공간이 매우 넓고 복잡하다.

또한, 할당기를 구현할 때는 C언어의 타입 시스템이 제공하는 보호장치를 벗어나야 한다.
직접 포인터를 캐스팅하고, 포인터 연산을 다루어야 한다.
에러가 발생하기 쉽고, 디버깅도 쉽지 않을 것이다.

할당기는 코드 양이 많은 편은 아니다.
하지만 그만큼 작은 실수 하나에도 치명적인 문제가 발생할 수 있다.
한 줄, 한 비트라도 잘못 다루면 프로그램 전체가 잘못 동작할 수 있다.

특히, C++이나 Java 같은 고수준 언어 에 익숙한 사람이라면 이런 저수준 프로그래밍 스타일을 처음 접했을 때, 개념적인 장벽에 부딪히기 쉬울 것이다.

이 장벽을 넘기 위해 비교적 단순한 모델부터 시작한다.
묵시적 가용 리스트와 즉시 경계 태그 연결(Immediate Boundary-Tag Coalescing)을 기반으로 한 간단한 할당기를 직접 구현해보자.

다음은 구현 환경이다.

  • 블록 하나가 가질 수 있는 최대 크기는 232=4GB2^{32} = 4GB로 설정한다.
  • 작성하는 코드는 32비트 환경(gcc -m32) 또는 64비트 환경(gcc -m64)이다.
    별다른 수정 없이 바로 동작할 수 있는 것은 64비트이다.

1. 할당기 기본 설계

1) 메모리 모델

 1  /* Private global variables */
 2  static char *mem_start_brk;      /* 힙의 첫 번째 바이트를 가리키는 포인터 */
 3  static char *mem_brk;       /* 현재 힙의 끝(마지막 바이트 + 1)을 가리키는 포인터 */
 4  static char *mem_max_addr;  /* 허용 가능한 힙 최대 주소 + 1 */
 5 
 6  /*
 7   * mem_init - 메모리 시스템 모델 초기화
 8   */
 9  void mem_init(void)
10  {
11      mem_start_brk = (char *)Malloc(MAX_HEAP);          /* 힙 공간 할당 */
12      mem_brk = (char *)mem_start_brk;                    /* 힙 끝을 힙 시작과 동일하게 초기화 */
13      mem_max_addr = (char *)(mem_start_brk + MAX_HEAP);  /* 힙 최대 주소 설정 */
14  }
15 
16  /*
17   * mem_sbrk - sbrk 함수의 간단한 모델
18   *            힙을 incr 바이트만큼 확장하고,
19   *            새 영역의 시작 주소를 반환한다.
20   *            이 모델에서는 힙을 줄일 수 없다.
21   */
22  void *mem_sbrk(int incr)
23  {
24      char *old_brk = mem_brk;
25 
26      if ((incr < 0) || ((mem_brk + incr) > mem_max_addr)) {
27          errno = ENOMEM;  /* 메모리 부족 에러 설정 */
28          fprintf(stderr, "ERROR: mem_sbrk failed. Ran out of memory...\n");
29          return (void *)-1;  /* 실패 시 -1 반환 */
30      }
31      mem_brk += incr;  /* 힙 포인터를 incr만큼 증가 */
32      return (void *)old_brk; /* 확장 전 힙 포인터 반환 */
}

우리가 만들 할당기는 memlib.c 패키지에서 제공하는 메모리 시스템 모델을 사용한다.
이 모델을 사용하는 이유는, 기존 시스템 malloc을 건드리지 않고 만들 할당기만 따로 실험할 수 있게 하기 위함이다.

mem_init 함수는 힙에 사용할 수 있는 가상 메모리를 더블워드(double-word) 정렬된 큰 바이트 배열로 모델링한다.

  • mem_start_brk ~ mem_brk 사이의 바이트: 이미 할당된 가상 메모리
  • mem_brk 이후의 바이트: 아직 할당되지 않은 가상 메모리

할당기가 추가 메모리가 필요할 경우, mem_sbrk 함수를 호출하여 가상의 힙을 확장한다.
mem_sbrk는 시스템의 sbrk와 인터페이스 및 동작은 같지만, 힙을 줄이는 요청은 거부한다는 점이 다르다.

2) 할당기 코드 구조

할당기 코드는 mm.c라는 소스 파일에 작성한다.
사용자는 이 파일을 컴파일하고 프로그램에 연결(link)하여 사용할 수 있다.

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

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

  1. mm_init(void)
    할당기를 초기화하는 함수이다.
    성공하면 0, 실패하면 -1을 반환한다.

  2. mm_malloc(size_t size)
    요청한 크기(size)만큼 메모리를 할당한다.

  3. mm_free(void *ptr)
    주어진 포인터(ptr)가 가리키는 메모리를 해제한다.

이 함수들의 인터페이스와 동작은 시스템 malloc/free와 동일하게 설계되어 있다.

3) 블록 포맷과 free list 구조

할당기는 아래의 블록 포맷을 따른다.

  • 블록 하나는 기본적으로 header와 footer를 가지고 있다.
  • 정렬을 고려했을 때, 최소 16바이트 이상의 크기를 갖는다.

free list는 묵시적 가용 리스트 형태로 관리되며, 그 기본 형태는 아래와 같다.

4) 힙(heap)의 초기 구조

힙은 다음과 같은 특별한 구조로 시작된다.

  1. 패딩 워드(Padding Word)
    더블워드 경계(double-word boundary)에 맞추기 위한 사용되지 않는 공간이다.

  2. 프롤로그 블록(Prologue Block)
    8바이트 크기의 할당된 블록이다.
    오직 header와 footer만 존재한다.
    힙 초기화 시 생성되며, 절대 free되지 않는다.

  3. 일반 블록들
    이후에는 사용자의 malloc이나 free 호출에 따라 생성되는 일반 블록들이 이어진다.

  4. 에필로그 블록(Epilogue Block)
    header만으로 구성된, 크기가 0으로 할당된 블록이다.

프롤로그와 에필로그 블록들은 연결 과정에서 발생할 수 있는 가장자리 문제를 없애기 위한 속임수다.
할당기는 한 개의 정적(static) 전역변수를 사용하여 항상 프롤로그 블록을 가리키도록 한다.
(참고로, 작은 최적화를 통해 프롤로그 블록 대신 "프롤로그 다음 블록"을 가리키게 설정할 수도 있다.)

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

아래 코드는 할당기 코드 전반에서 사용할 기본 상수와 매크로를 정의한다.

 1  /* 기본 상수와 매크로 */
 2  #define WSIZE      4			/* 워드(Word) 및 헤더/푸터 크기 (bytes) */
 3  #define DSIZE      8			/* 더블워드(Double Word) 크기 (bytes) */
 4  #define CHUNKSIZE  (1 << 12)	/* 힙을 이만큼 확장 (bytes) = 4KB */
 5  
 6  #define MAX(x, y) ((x) > (y) ? (x) : (y))   /* 두 값 중 더 큰 값을 반환 */
 7  
 8  /* 크기(size)와 할당(allocated) 비트를 하나의 워드로 묶기 */
 9  #define PACK(size, alloc) ((size) | (alloc))
10  
11  /* 주소 p에 저장된 워드를 읽거나(p), val 값을 p에 저장하기 */
12  #define GET(p)      (*(unsigned int *)(p))           	/* p가 가리키는 곳의 값을 읽음 */
13  #define PUT(p, val) (*(unsigned int *)(p) = (val))   	/* p가 가리키는 곳에 val 값을 저장 */
14  
15  /* 주소 p로부터 블록의 크기(size)와 할당 여부(allocated) 추출 */
16  #define GET_SIZE(p)  (GET(p) & ~0x7)	/* 하위 3비트를 제외한 나머지가 size */
17  #define GET_ALLOC(p) (GET(p) & 0x1)		/* 가장 마지막 비트가 할당 여부(1이면 할당됨) */
18  
19  /* 블록 포인터 bp를 기준으로, header와 footer의 주소 계산 */
20  #define HDRP(bp) ((char *)(bp) - WSIZE)							/* 블록의 헤더 주소 */
21  #define FTRP(bp) ((char *)(bp) + GET_SIZE(HDRP(bp)) - DSIZE)	/* 블록의 푸터 주소 */
22  
23  /* 블록 포인터 bp를 기준으로, 다음 블록과 이전 블록의 주소 계산 */
24  #define NEXT_BLKP(bp) ((char *)(bp) + GET_SIZE(((char *)(bp) - WSIZE))) /* 다음 블록 포인터 */
25  #define PREV_BLKP(bp) ((char *)(bp) - GET_SIZE(((char *)(bp) - DSIZE))) /* 이전 블록 포인터 */

1) 기본 상수 정의

2~4번째 줄은 기본적인 크기 상수를 정의한다.

  • WSIZE: 워드 크기
  • DSIZE: 더블워드 크기
  • CHUNKSIZE: 초기 free 블록 크기과 힙 확장을 위한 기본 크기

2) header/footer 조작을 위한 매크로

free list 안에서 header와 footer를 직접 다루는 것은 까다롭다.
형변환(casting)과 포인터 연산(pointer arithmetic)을 많이 써야 하기 때문이다.
9~25번째 줄에서는 free list에 접근하고 방문하는 PACK, GET, PUT 매크로를 정의한다.

  • PACK: size 값과 할당 여부 비트를 하나로 합쳐서 header나 footer에 저장할 수 있는 값을 만든다. (9번째 줄)
  • GET: 인자 p가 가리키는 위치의 워드(4바이트)를 읽어서 반환한다. (12번째 줄)
    여기서 형변환은 매우 중요한데, void* 타입은 바로 역참조할 수 없기 때문에 반드시 unsigned int*로 캐스팅해야 하기 때문이다.
  • PUT: 인자 p가 가리키는 위치에 val 값을 저장한다. (13번째 줄)

3) 블록 메타데이터 읽기 매크로

16~17번째 줄의 GET_SIZE, GET_ALLOC 매크로는 주소 p에서 각각 블록의 크기(size)와 할당 여부를 추출하는 역할을 한다.

  • GET_SIZE: 하위 3비트(0x7)를 제거하고 남은 부분으로 블록 크기를 구한다.
  • GET_ALLOC: 가장 마지막 비트(0x1)를 통해 할당 여부를 확인한다.

4) 블록 간 이동을 위한 매크로

16~25번째 줄의 나머지 매크로들은 블록 포인터(bp)를 기반으로 동작한다.
bp는 블록의 payload 첫 바이트를 가리키는 포인터다.

  • HDRP(bp): 주어진 bp로부터 블록의 header 주소를 계산한다.
  • FTRP(bp): bp 기준으로 블록의 footer 주소를 계산한다.
  • NEXT_BLKP(bp): 현재 블록(bp)에서 다음 블록의 포인터를 계산한다.
  • PREV_BLKP(bp): 현재 블록(bp)에서 이전 블록의 포인터를 계산한다.

이 매크로들은 조합해서 다양한 방식으로 free list를 조작할 수 있다.

5) 매크로 조합 사용 예시

현재 블록의 포인터 bp가 주어졌을 때, 다음 블록의 크기를 구하고 싶다면 다음처럼 코드를 작성할 수 있다.

size_t size = GET_SIZE(HDRP(NEXT_BLKP(bp)));
  • bp: NEXT_BLKP로 다음 블록 위치로 이동한다.
  • NEXT_BLKP(bp): HDRP로 다음 블록의 header 주소를 찾는다.
  • HDRP(NEXT_BLKP(bp)): GET_SIZE로 다음 블록의 크기를 읽는다.

3. 초기 가용 리스트 만들기

1) mm_init 함수

 1  int mm_init(void)
 2  {
 3      /* 초기 비어있는 힙 생성 */
 4      if ((heap_listp = mem_sbrk(4 * WSIZE)) == (void *)-1)
 5          return -1;
 6      PUT(heap_listp, 0);                       	   /* 정렬을 위한 패딩 */
 7      PUT(heap_listp + (1 * WSIZE), PACK(DSIZE, 1)); /* 프롤로그 헤더 (8바이트, 할당 표시) */
 8      PUT(heap_listp + (2 * WSIZE), PACK(DSIZE, 1)); /* 프롤로그 푸터 (8바이트, 할당 표시) */
 9      PUT(heap_listp + (3 * WSIZE), PACK(0, 1));     /* 에필로그 헤더 (크기 0, 할당 표시) */
10      heap_listp += (2 * WSIZE);                     /* heap_listp를 프롤로그 블록의 payload 부분으로 이동 */
11 
12      /* CHUNKSIZE 바이트 크기의 새로운 free block으로 힙 확장 */
13      if (extend_heap(CHUNKSIZE / WSIZE) == NULL)
14          return -1;
15      return 0;
16  }

할당기를 사용하기 전에 반드시 mm_init 함수를 호출해 힙을 초기화해야 한다.
호출 후, mm_init 함수는 메모리 시스템에서 4개의 워드를 가져와서 빈 가용 리스트(4~10번째 줄)를 만든다.

2) extend_heap 함수

 1  static void *extend_heap(size_t words)
 2  {
 3      char *bp;
 4      size_t size;
 5  
 6      /* 정렬을 유지하기 위해 짝수 개의 워드를 할당 */
 7      size = (words % 2) ? (words + 1) * WSIZE : words * WSIZE;
 8      if ((long)(bp = mem_sbrk(size)) == -1)
 9          return NULL;
10  
11      /* 새로 만든 free block의 헤더/푸터와 새로운 에필로그 헤더 초기화 */
12      PUT(HDRP(bp), PACK(size, 0));              /* Free block 헤더 */
13      PUT(FTRP(bp), PACK(size, 0));              /* Free block 풋터 */
14      PUT(HDRP(NEXT_BLKP(bp)), PACK(0, 1));      /* 새로운 에필로그 헤더 */
15  
16      /* 이전 블록이 free였다면 연결(coalesce) 시도 */
17      return coalesce(bp);
18  }

그 다음 extend_heap 함수를 호출하여 힙을 CHUNKSIZE만큼 확장하고, 첫 번째 free 블록을 생성한다.
이 과정을 통해 할당기는 초기화되고, 이후부터 메모리 할당과 해제 요청을 정상적으로 처리할 수 있다.

extend_heap 함수는 다음 두 경우에 호출된다.

  1. 처음 힙을 초기화할 때
  2. mm_malloc이 적당한 크기의 free 블록을 찾지 못했을 때

요청된 크기는 항상 2워드(8바이트) 단위로 올림하여 정렬한다.
그 다음 mem_sbrk를 통해 추가 힙 공간을 받아온다. (7~9번째 줄)

3) extend_heap 세부 동작

확장한 메모리는 다음과 같이 구성한다. (12~17번째 줄)

  • 메모리 맨 앞 부분은 새로운 free 블록의 헤더가 된다.
  • 메모리 맨 끝 부분은 새로운 에필로그 블록의 헤더가 된다.

힙은 항상 8바이트 경계로 정렬되어 있어야 하기 때문에, mem_sbrk로 받아온 메모리는 바로 사용할 수 있다.
또한 확장 전 힙의 마지막 블록이 free 상태였다면, 새로운 free 블록과 합쳐(coalescing) 하나의 큰 블록으로 만든다.

4. 블록 반환과 연결

 1  void mm_free(void *bp)
 2  {
 3      size_t size = GET_SIZE(HDRP(bp));
 4  
 5      PUT(HDRP(bp), PACK(size, 0));    /* 헤더를 free 상태로 설정 */
 6      PUT(FTRP(bp), PACK(size, 0));    /* 푸터를 free 상태로 설정 */
 7      coalesce(bp);                   /* 인접한 free 블록들과 연결(coalesce) 시도 */
 8  }
 9 
10  static void *coalesce(void *bp)
11  {
12      size_t prev_alloc = GET_ALLOC(FTRP(PREV_BLKP(bp))); /* 이전 블록 할당 여부 */
13      size_t next_alloc = GET_ALLOC(HDRP(NEXT_BLKP(bp))); /* 다음 블록 할당 여부 */
14      size_t size = GET_SIZE(HDRP(bp));                   /* 현재 블록 크기 */
15 
16      if (prev_alloc && next_alloc) { /* Case 1: 앞뒤 모두 할당된 경우 */
17          return bp;
18      }
19  
20      else if (prev_alloc && !next_alloc) { /* Case 2: 앞은 할당, 뒤는 free */
21          size += GET_SIZE(HDRP(NEXT_BLKP(bp)));
22          PUT(HDRP(bp), PACK(size, 0));
23          PUT(FTRP(bp), PACK(size, 0));
24      }
25 
26      else if (!prev_alloc && next_alloc) { /* Case 3: 앞은 free, 뒤는 할당 */
27          size += GET_SIZE(HDRP(PREV_BLKP(bp)));
28          PUT(FTRP(bp), PACK(size, 0));
29          PUT(HDRP(PREV_BLKP(bp)), PACK(size, 0));
30          bp = PREV_BLKP(bp); /* bp를 앞 블록으로 이동 */
31      }
32 
33      else { /* Case 4: 앞뒤 모두 free */
34          size += GET_SIZE(HDRP(PREV_BLKP(bp))) + GET_SIZE(FTRP(NEXT_BLKP(bp)));
35          PUT(HDRP(PREV_BLKP(bp)), PACK(size, 0));
36          PUT(FTRP(NEXT_BLKP(bp)), PACK(size, 0));
37          bp = PREV_BLKP(bp); /* bp를 앞 블록으로 이동 */
38      }
39 
40      return bp;
41  }

프로그램은 mm_free 함수를 호출하여 기존에 할당받았던 블록을 해제한다.
mm_free는 요청된 블록(bp)을 해제한 다음, 경계 태그(boundary tags)를 이용해 인접한 가용 블록들을 병합(coalescing)한다.

coalesce 보조 함수는 그림 경계 태그의 4가지 경우를 직접 구현한 것이다.

여기에는 약간 미묘한 부분이 하나 있다.

우리가 선택한 free list 포맷(항상 할당된 것으로 표시된 프롤로그/에필로그 블록 포함)은, 요청된 블록(bp)이 힙의 맨 앞이나 맨 끝에 있을 때 발생할 수 있는 귀찮은 특수 상황(edge condition)을 무시할 수 있게 해준다.

이런 특별한 블록이 없다면, 코드가 훨씬 지저분하고, 에러가 많이 발생하고, 느려졌을 것이다.
왜냐하면 free를 할 때마다 이런 드문 특수 상황을 매번 검사해야 하기 때문이다.

5. 블록 할당

 1  void *mm_malloc(size_t size)
 2  {
 3      size_t asize;        /* 조정된 블록 크기 (overhead 및 alignment 포함) */
 4      size_t extendsize;   /* 적당한 free block이 없을 경우 힙을 확장할 크기 */
 5      char *bp;
 6 
 7      /* 잘못된 요청 무시 */
 8      if (size == 0)
 9          return NULL;
10 
11      /* 블록 크기 조정 (헤더/푸터 공간과 정렬 요건 포함) */
12      if (size <= DSIZE)
13          asize = 2 * DSIZE; /* 최소 블록 크기: header + footer + payload */
14      else
15          asize = DSIZE * ((size + (DSIZE) + (DSIZE-1)) / DSIZE); /* 8바이트 단위로 반올림 */
16 
17      /* free list에서 적당한 블록 찾기 */
18      if ((bp = find_fit(asize)) != NULL) {
19          place(bp, asize); /* 찾은 블록에 배치(place) */
20          return bp;
21      }
22 
23      /* 적당한 블록이 없는 경우: 힙을 확장한 후 배치 */
24      extendsize = MAX(asize, CHUNKSIZE); /* 필요한 크기와 기본 CHUNKSIZE 중 더 큰 값 선택 */
25      if ((bp = extend_heap(extendsize / WSIZE)) == NULL)
26          return NULL;
27      place(bp, asize);
28      return bp;
29  }

1) 메모리 요청(size)

프로그램은 mm_malloc 함수를 호출하여 원하는 크기(size)만큼 메모리를 요청한다.

2) 잘못된 요청 거르기 (7~9줄)

요청한 size가 0이면, 아무것도 할당하지 않고 NULL을 반환한다.

3) 블록 크기 조정 (11~15줄)

할당기는 요청된 블록 크기를 조정하여, header/footer 공간을 확보하고 더블워드 정렬을 만족시켜야 한다.

  • size <= DSIZE인 경우 : 최소 블록 크기를 16바이트로 설정한다.
    • 8바이트: payload를 위한 공간
    • 8바이트: header과 footer 오버헤드
  • size > DSIZE인 경우: size에 오버헤드 공간을 더한 뒤, 8바이트 단위로 올림한다.

4) free list 탐색 (17~21줄)

조정된 크기(asize)를 만족하는 적당한 가용 블록을 free list에서 탐색한다.

  • 찾은 경우, place() 함수를 호출하여 블록을 배치하고, 포인터를 반환한다.

5) 힙 확장 (23~28줄)

적절한 블록을 찾지 못했다면, 힙을 확장하여 새로운 free block을 만든다.

  • 확장 크기(extend size)는 asize와 CHUNKSIZE 중 더 큰 값으로 결정한다.
  • 확장 후, 새 블록에 배치하고 포인터를 반환한다.
profile
은채
이전 포스트

[Malloc Lab-2] CSAPP 9.9 동적 메모리 할당 (11) : 경계 태그로 연결하기

다음 포스트

[Malloc Lab-2] CSAPP 9.9 동적 메모리 할당 (13) : 명시적 가용 리스트

0개의 댓글