[C] Malloc 구현: 묵시적 가용 리스트 사용

방법이있지·2025년 6월 27일
C크래프톤 정글

[정글 4-8주차] C언어

목록 보기
24/26
post-thumbnail

계속 정글에서 공부한 내용을 블로그로 정리하며 느껴지는 점은,

과제의 난이도가 높아지고 분량이 길어질수록 코드를 일일이 블로그에 설명할 순 없다는 점입니다.

그래서 노선을 바꿔서, 이제부턴 모든 코드를 일일이 설명하기보단 중요한 부분만 개념과 엮어서 설명해 보려고 합니다. 그리고 완벽히 정리해야 한다는 생각을 버리고 좀 두서없이 정리해 보겠습니다. 대신 코드는 테스트케이스를 통과했으니 두서 있을(?) 거에요.

이번 글엔 묵시적 리스트를 통해 Malloc 함수를 구현한 과정을 정리해 봤습니다.

매크로 함수 등 설정은 CSAPP 책 9.9.12절에 잘 나와 있습니다.

전체 코드는 깃허브에서 확인 가능합니다

묵시적 가용 리스트

자세한 설명은 이 글 참고 바람

  • 가용 리스트는, 힙 내부의 메모리 할당이 가능한 가용 블록(이하 빈 블록)을 관리하는 리스트입니다.
    • 실제 malloc 함수는 가용 리스트를 살펴보며, 어떤 빈 블록에 메모리를 할당할지 결정합니다.
  • 가용 리스트는 묵시적 vs 명시적 가용 리스트로 나뉩니다.
    • 명시적 가용 리스트의 경우, 빈 블록들만을 연결한 연결 리스트 등 자료구조를 이용해 구현됩니다. (이건 추후 다른 글로 정리해보겠습니다.)
    • 반면 묵시적 가용 리스트는 별도의 자료구조로 구현되지 않습니다. 대신 각 블록의 헤더에 블록 자기 자신의 크기를 저장해 둡니다. 헤더를 참고하여 다음 블록의 주소를 계산하는 식으로, 리스트 탐색이 이루어집니다.

  • 각 블록의 주소는, 헤더의 시작 주소가 아니라, 헤더 이후 실제 유효 데이터(이하 payload)의 시작 주소입니다. 이거 굉장히 헷갈리기 쉬우니 조심합니다.
    • e.g., 한 블록의 헤더가 주소 0x100에 있다면, 헤더는 4바이트이므로 블록의 시작주소는 0x104입니다.
  • 헤더 및 푸터에는 (블록의 크기 / 할당 여부)가 저장됩니다.
    • 블록의 크기는 payload + 헤더 + 패딩 바이트 + 푸터를 모두 포합합니다.
    • 할당 여부의 경우, 할당됐으면 1, 비어있으면 0입니다. 이를 할당 비트라고 합니다.

mm_init: 힙 초기화

  • 본 예제에선 아래와 같은 조건을 가정합니다.
    • 블록의 헤더 및 푸터의 크기는 4바이트
    • 블록은 8바이트 단위로 정렬되어야 함 -> 즉 블록의 시작 주소는 8의 배수여야 함
    • 블록의 최소 크기는 16바이트
      • 헤더 4바이트 + 최소 1바이트 할당 + 푸터 4바이트
      • 합은 9바이트인데, 정렬 조건에 따라 8의 배수로 올림하면 16바이트.
      • 결국 최종 헤더 4바이트 + payload 1바이트 + 패딩 7바이트 + 푸터 4바이트

  • 힙을 초기화했을 때, 묵시적 가용 리스트는 다음과 같이 16바이트로 구성됩니다.

    • 사용되지 않는 4바이트 (각 블록의 시작 주소가 8의 배수가 될 수 있게, 정렬 용도로 놔둡니다)
    • 프롤로그 블록 (헤더 4바이트 + 푸터 4바이트 = 8바이트. 할당 상태.)
    • 에필로그 블록 (헤더 4바이트 / 하지만 마지막 블록임을 알리기 위해, 헤더 크기 정보엔 0바이트로 표시됨. 할당 상태.)

  • 프롤로그 블록을 가리키는 전역 포인터 static char *heap_listp를 사용하게 됩니다.

    • 앞서 말했듯이, 헤더의 주소가 아니라 헤더 직후의 주소를 가리킴에 유의합시다.

  • 힙을 초기화한 이후에는 실제 데이터를 할당할 수 있게, 힙을 확장해야 합니다.

    • 힙을 확장하는 방법은 다음 절에서 다룹니다.
// 힙을 초기화. 성공하면 0, 실패하면 -1 반환.
int mm_init(void)
{
    // mem_init()은 해줄 필요 없음. 이미 mdriver.c 파일에서 자동 실행됨.

	// WSIZE: 4바이트, DSIZE: 8바이트
    // (1) 메모리 시스템에서 4워드(16바이트)를 가져와서, 빈 가용 리스트를 만듦
    heap_listp = (char *)mem_sbrk(4 * WSIZE);   // 할당된 메모리의 시작주소
    if (heap_listp == (void *) -1) return -1;   // 메모리 할당에 실패했을 때

    // (2) 16바이트를 채워야 함
    PUT(heap_listp, 0);                             // (A) 맨 처음 비어 있는 4바이트
    PUT(heap_listp + WSIZE, PACK(DSIZE, 1));        // (B) 프롤로그 블록의 헤더 (8 / 1)
    PUT(heap_listp + WSIZE * 2, PACK(DSIZE, 1));    // (C) 프롤로그 블록의 푸터 (8 / 1)
    PUT(heap_listp + WSIZE * 3, PACK(0, 1));        // (D) 에필로그 블록의 헤더 (실제론 4바이트, 표시는 (0 / 1))

    // (3) 가용 블록을 생성??
    heap_listp += WSIZE * 2;                        // 프롤로그 블록의 헤더 직후 위치
    
    // 힙 확장하기 (CHUNKSIZE: 4096바이트)
    if (extend_heap(CHUNKSIZE / WSIZE) == NULL)
        return -1;
    return 0;
}

extend_heap: 힙 확장하기

  • (1) 위처럼 힙을 초기화했을 때, (2) 메모리 할당 요청을 받았는데 할당 가능한 빈 블록을 찾지 못했을 때...는 힙을 확장해야 합니다.
  • 본 예제에선 한 번에 4096바이트씩 확장합니다. 단, 요청된 메모리 크기가 4096바이트보다 큰 경우, 요청된 메모리 크기만큼 확장합니다.
  • 힙을 확장한 후에, 확장된 크기에 새로운 빈 블록이 생깁니다. 빈 블록이니까 할당 비트는 0이겠죠.
    • 이때 원래 에필로그 블록이 있던 자리에, 새로운 블록의 헤더가 들어옵니다.
    • 새로 확장된 영역의 마지막 4바이트에, 에필로그 블록의 헤더가 재배치됩니다.
    • 실제 데이터가 저장될 payload는 그 사이에 위치합니다.
  • 만약 이때 생성된 블록 앞에 가용 블록이 있으면, 두 가용 블록은 병합됩니다. 어떻게 병합이 이루어지는지는 후술합니다.
    • 실제로는 병합까지 마무리된 후, 블록의 주소가 반환됩니다.

// 힙이 초기화될 때 OR mm_malloc이 fit을 찾지 못했을 때, 힙을 요청크기(words)만큼 확장한다. 이후 새롭게 생긴 블록의 주소를 반환한다.
// words는 워드 단위로 입력받으며, 1워드 = 4바이트 이다.
static void *extend_heap(size_t words){
    size_t size = ALIGN(words * WSIZE);
    char *bp;

    // mem_sbrk(size)`는 힙 영역을 `size`만큼 늘려주고, 연장된 영역의 시작 주소를 반환
    bp = mem_sbrk(size);                        // 새로 할당된 블록의 포인터
    if (bp == (void *) -1) return NULL;         // 메모리 할당에 실패했을 때

    // 이전 에필로그 블록 자리에, 새로운 헤더가 옴
    PUT(HDRP(bp), PACK(size, 0));                       // 헤더

    // 새로운 푸터 및 에필로그 블록
    PUT(FTRP(bp), PACK(size, 0));                       // 푸터
    PUT(HDRP(NEXT_BLKP(bp)), PACK(0, 1));               // 에필로그 블록
    
    // Coalesce 함수로 병합
    return coalesce(bp);
}

mm_free: 블록 반환하기

  • 블록을 반환하는 경우는, 단순히 해당 블록 헤더 / 푸터의 할당 비트를 1에서 0으로 바꿔주면 됩니다.
  • 이후 반환된 블록 앞 / 뒤에 가용 블록이 있으면, 병합이 이루어질 수 있습니다. 후술하겠습니다.
// ptr가 가리키는 블록에 할당된 메모리를 반환한다. 반환값은 없다.
void mm_free(void *ptr)
{
    
    // 그러면 해당 주소의 할당 비트는 1 -> 0이 되지 않을까?
    size_t size = GET_SIZE(HDRP(ptr));
    PUT(HDRP(ptr), PACK(size, 0));
    PUT(FTRP(ptr), PACK(size, 0));

    // 인접 가용 블록을 통합
    coalesce(ptr);
}

coalesce: 블록 병합하기

  • 블록을 병합할 때는, 현재 블록 앞뒤 블록이 비었는지 할당됐는지 확인해야 합니다. 비어 있는 경우에만 병합을 할 수 있기 때문에 그렇겠죠.
  • 헤더의 할당 비트가 1이면 할당된 거고 0이면 비었다는 거 기억하시죠?

블록병합

  • (1) 직전, 직후 블록 모두 할당 상태
    • 연결이 불가능하니까 건너뜁니다.
  • (2) 직전 블록은 할당 상태, 직후 블록은 빈 상태
    • 반환된 블록과 직후 블록이 연결됩니다. 이때 현재 블록의 헤더와 직후 블록 푸터의 크기 정보를, 두 블록의 크기를 합한 것으로 갱신
  • (3) 직전 블록은 빈 상태, 직후 블록은 할당 상태
    • 직전 블록과 반환된 블록이 연결됩니다. 이때 직전 블록의 헤더와 현재 블록의 푸터를, 두 블록의 크기를 합한 것으로 갱신합니다.
  • (4) 직전, 직후 블록 모두 가용 상태
    • 세 블록이 모두 연결됩니다. 이때 직전 블록의 헤더와 현재 블록의 푸터를, 두 블록의 크기를 합한 것으로 갱신합니다.
// ptr이 가리키는 블록 전후에 가용 블록이 있으면 통합한다.
// 통합된 블록의 시작 주소를 반환한다.
static void *coalesce(void *ptr){
    size_t prev_alloc = GET_ALLOC(FTRP(PREV_BLKP(ptr)));    // 이전블록 할당비트
    size_t next_alloc = GET_ALLOC(HDRP(NEXT_BLKP(ptr)));    // 다음블록 할당비트
    size_t size = GET_SIZE(HDRP(ptr));

	// 1(할당)이면 참, 0(비었음)이면 거짓... 기본이죠?
    if (prev_alloc && next_alloc){
        // 연결 불가능. 넘어가기.
    } else if (prev_alloc) {
        // 비어 있는 다음 블록과 연결 가능.
        size += GET_SIZE(HDRP(NEXT_BLKP(ptr)));     // 다음 블록의 크기 더하기
        PUT(HDRP(ptr), PACK(size, 0));             // 현재 블록의 헤더 수정
        PUT(FTRP(ptr), PACK(size, 0));             // 다음 블록의 푸터 수정
        // 이때 FTRP(NEXT_BLKP(ptr))이 아니라 그냥 FTRP(ptr) 해 줘야 합니다
        // 헤더의 크기정보를 수정하면서 두 블록이 이미 통합된 상황이라 그렇습니다
       
    } else if (next_alloc) {
        // 이전 블록과 연결 가능.
        size += GET_SIZE(HDRP(PREV_BLKP(ptr)));     // 이전 블록의 크기 더하기
        PUT(FTRP(ptr), PACK(size, 0));             // 현재 블록의 푸터 수정
        PUT(HDRP(PREV_BLKP(ptr)), PACK(size, 0));  // 이전 블록의 헤더 수정
        ptr = PREV_BLKP(ptr);                       // 통합된 블록으로 주소 갱신
    } else {
        // 이전, 다음 블록과 연결 가능.
        size += GET_SIZE(HDRP(PREV_BLKP(ptr)));     // 이전 블록의 크기 더하기
        size += GET_SIZE(FTRP(NEXT_BLKP(ptr)));     // 다음 블록의 크기 더하기
        PUT(HDRP(PREV_BLKP(ptr)), PACK(size, 0));  // 이전 블록의 헤더 수정
        PUT(FTRP(NEXT_BLKP(ptr)), PACK(size, 0));  // 다음 블록의 푸터 수정
        ptr = PREV_BLKP(ptr);                       // 통합된 블록으로 주소 갱신
    }
    return ptr;	// 통합된 블록의 포인터 반환
}

mm_malloc: 블록 할당하기

  • 드디어 드디어 블록을 할당할 때가 왔습니다. 신나지 않으세요? 난 너무 신나는데
  • (1) 실제로 할당될 블록의 크기를 계산해야 합니다.
    • 우리가 말록 함수에 size만 할당하라고 요청해도, 실제로는 거기에 헤더 4바이트, 푸터 4바이트까지 포함하여 할당이 됩니다.
    • 그리고 정렬 기준에 따라, 8의 배수의 값으로 올림해 줘야 합니다.
    • e.g., 13바이트 할당 요청 -> 13 + 4 (헤더) + 4 (푸터) = 21. 8의 배수로 올림하면 24. 즉 24바이트를 할당할 블록을 찾아야 함!

  • (2) 할당할 블록을 찾습니다.
    • 할당할 블록을 찾을 땐 First Fit 정책을 사용합니다. 가용 리스트를 처음부터 검색해서, 크기가 맞는 첫 번째 가용 블록을 반환하게 됩니다. First Fit 정책의 구현 방법은 후술합니다.
  • (3A) 할당할 블록을 찾은 경우, 할당합니다.
    • 할당을 어떻게 하는지 역시 후술합니다. 이 과정에서 블록이 분할될 수 있습니다.
  • (3B) 할당할 블록이 없는 경우, 힙을 연장해야 합니다.
    • 힙을 연장한 뒤, 새롭게 만들어진 블록에 할당합니다.
// size 바이트를 동적 할당해 달라고 요청한다.
// 할당된 블록의 시작 주소를 반환한다.
void *mm_malloc(size_t size)
{
    size_t asize;       // 실제로 할당되는 블록의 크기
    size_t extendsize;  // fit이 없는 경우 이만큼 힙을 연장
    char *bp;

    // size == 0인 경우 NULL을 반환
    if (size == 0) return NULL;

    // 현재 size에 헤더 + 푸터를 포함하고, 인접한 DSIZE(8바이트)의 배수로 올림 (패딩)
    asize = ALIGN(size + DSIZE);
        
    // 할당할 블록 정하기 -> first fit 사용
    bp = find_fit(asize);
    if (bp != NULL){
        place(bp, asize);   // 주소 bp에서 asize만큼 할당
        return bp;          // 할당된 블록 주소 반환 
    }

    // 맞는 칸이 없으면 힙을 연장
    extendsize = MAX(asize, CHUNKSIZE);
    bp = extend_heap(extendsize / WSIZE);

    if (bp == NULL){
        // 힙 연장에 실패한 경우
        return NULL;
    } else {
        // 새로 연장하면서 생긴 영역에 할당
        place(bp, asize);
        return bp;
    }
}

find_fit: 할당할 블록 찾기 구현 (First Fit)

  • First Fit으로, 묵시적 가용 리스트를 처음부터 탐색하면서 할당할 블록을 찾아야 합니다.
  • 각 블록의 헤더를 참고하여, 블록의 크기 및 할당 비트를 확인해 두 조건을 모두 만족하는지 확인합니다.
    • (1) 할당해야 하는 크기 <= 블록의 크기이고 (이때 할당해야 하는 크기는 헤더 + 푸터 + 패딩비트를 포함한 크기입니다. 아래 코드 기준 asize임.)
    • (2) 할당비트 == 0일 때 (즉 빈 블록일 때)
  • 두 조건을 모두 만족하면, 해당 블록의 주소를 반환합니다.
  • 만족하지 않으면 계속 탐색해야 합니다. 헤더의 블록 크기 정보를 활용하여, 다음 블록의 주소를 계산해 넘어갑니다.
// 묵시적 가용 리스트에서 first fit 검색을 수행.
// 크기 asize를 저장할 수 있는 첫 블록의 주소를 반환. 찾지 못하면 NULL 반환.
static void *find_fit(size_t asize){
    void *bp;      // 현재 검색중인 블록
    size_t block_size;          // 현재 블록의 크기
    // 에필로그 블록 도달 시 종료
    for (bp = heap_listp; (block_size = GET_SIZE(HDRP(bp))) != 0; bp = NEXT_BLKP(bp)){
        // 사이즈에 맞는 가용 블록이 있는 경우, 해당 블록 주소를 반환
        if (asize <= block_size && GET_ALLOC(HDRP(bp)) == 0){
            return bp;
        }
    }
    return NULL;
}

place: 블록 할당하고 분할하기

  • 할당할 블록을 정한 후엔, 실제 블록에서 메모리가 할당되는 크기(아래 함수 기준 asize) 및 나머지 부분의 크기 (아래 함수 기준 rest_size)를 계산해야 합니다.
    • 헤더를 통해 블록의 크기를 구한 후, 실제 할당되는 메모리 크기를 빼 주면 나머지 부분의 크기를 계산할 수 있습니다.
  • 나머지 부분의 크기 >= 블록의 최소 크기인 경우, 나머지 부분을 별도의 빈 블록으로 분리해 나중에 할당될 수 있게 합니다.
    • 본 예제에선 블록의 최소 크기를 16바이트로 둔 점, 기억하고 계시길 바랍니다/
    • 할당되는 부분 / 나머지 부분 각각 헤더, 푸터를 설정해 줍니다.
    • 할당되는 부분의 헤더, 푸터에는 실제 할당되는 메모리 크기를 저장하고, 할당비트는 1로 설정합니다.
    • 나머지 부분의 헤더, 푸터에는 나머지 부분의 크기를 저장하고, 할당비트는 0
  • 나머지 부분의 크기 < 블록의 최소 크기인 경우, 블록의 분할 없이 할당합니다.
    • 현재 블록의 헤더, 푸터의 할당비트만 0에서 1로 바꿔 줍니다.
// 주소 bp의 블록에 asize만큼 메모리를 할당
// 할당된 블록의 주소를 반환
static void place(void *bp, size_t asize){
    size_t curr_size, rest_size;
    
    // 나머지 부분의 크기를 계산한다
    curr_size = GET_SIZE(HDRP(bp));
    rest_size = curr_size - asize;

    if (rest_size >= 4 * WSIZE){
        // 최소 블록 크기 (4 * 4바이트 = 16바이트) 이상인 경우 분할을 수행한다

        // 앞 블록의 헤더
        PUT(HDRP(bp), PACK(asize, 1));
        // 앞 블록의 푸터
        PUT(FTRP(bp), PACK(asize, 1));
        // 뒷 헤더 만들기
        PUT(HDRP(NEXT_BLKP(bp)), PACK(rest_size, 0));
        // 뒷 블록의 푸터 만들기
        PUT(FTRP(NEXT_BLKP(bp)), PACK(rest_size, 0));
    } else {
        // 최소 블록 크기 이상이 아닌 경우, 분할을 수행하지 않는다
        // 헤더, 푸터만 0에서 1로 바꾸기
        PUT(HDRP(bp), PACK(curr_size, 1));
        PUT(FTRP(bp), PACK(curr_size, 1));
    }
}

mm_realloc: 할당된 메모리의 크기를 변경하기

  • 본 구현에선 단순히 앞서 만둔 mm_malloc / mm_free 함수를 재사용해서 구현했습니다.
  • 이 경우 할당된 블록을 가리키는 포인터 ptr과, 변경할 크기 size를 매개변수로 받게 됩니다. 단, 두가지 예외 경우를 고려합시다.
  • ptr이 널포인터인 경우, mm_malloc(size)와 동일하게 단순히 size 크기만큼 메모리를 할당하고, 블록의 시작 주소를 반환합니다.
  • size가 0인 경우, mm_free(ptr)와 동일하게 해당 블록에 할당된 메모리를 반환합니다.
  • 우선 mm_malloc(size)로, 변경할 크기만큼의 메모리 공간을 할당받습니다.
  • 이후 기존 블록에 있던 데이터를 새로 할당받은 블록으로 복사해야 합니다.
    • 이때 (기존 블록의 크기 < 새로 할당된 크기)인 경우, 기존 블록 전체가 복사됩니다.
      • 예를 들어 기존 블록이 8바이트고 새로 할당받은 블록이 12바이트면, 8바이트 전체가 복사됩니다.
    • 단 (기존 블록의 크기 > 새로 할당된 크기)인 경우, 기존 블록 중 새로 할당된 크기에 해당되는 앞부분만 복사됩니다.
      • 예를 들어 기존 블록이 12바이트고 새로 할당받은 블록이 8바이트라면, 12바이트 중 앞 8바이트만 복사됩니다.
    • 즉 기존 블록의 크기 (헤더로 확인)와 새로 할당된 크기 (size 매개변수) 중 최솟값만큼 복사를 하면 되겠지요.
  • 마지막으로 mm_free로 기존 블록의 메모리 할당을 해제하고, 새롭게 할당받은 포인터를 반환하면 되겠습니다.
// ptr가 가리키는 블록에 할당된 메모리의 크기를 size로 변경
void *mm_realloc(void *ptr, size_t size)
    if (ptr == NULL){
      // ptr가 NULL -> mm_malloc(size)와 동일.
        return mm_malloc(size);
    } else if (size == 0){
      // size가 0 -> mm_free(ptr)과 동일.
        mm_free(ptr);
        return NULL;
    }

	// 현재 블록을 가리키는 포인터
    void *oldPtr = ptr;
    
    // 메모리 크기를 변경한 후, 블록을 가리키는 포인터
    void *newPtr = mm_malloc(size);

    // 이전 블록에서 복사해야 하는 데이터의 크기
    // (이전 블록의 크기), (새로운 블록의 크기) 중 더 작은 값
    size_t copySize = GET_SIZE(HDRP(ptr));
    if (size < copySize){
        copySize = size;
    }

    // 이전 블록의 내용을 새 블록으로 복사
    memcpy(newPtr, oldPtr, copySize);

    // 이전 블록에 할당된 메모리 free
    mm_free(oldPtr);

    return newPtr;
}

채점

정글에서 준 test case로 채점을 해 보면 100점 만점에 62점이 나옵니다.

  • util 점수: 메모리를 얼마나 효율적으로 사용했는지
    • 본 코드의 First Fit 기준으로는 무조건 첫 번째 가능한 블록에 할당을 하게 됩니다. 크기가 잘 맞지 않는 블록을 자주 사용하게 되어, 내부 단편화가 증가해 메모리를 효율적으로 사용하기 어렵습니다.
  • thru 점수: 1초에 몇 천개의 연산을 처리했는지
    • 묵시적 리스트의 경우 모든 블록을 선형 탐색해야 합니다. 보다 빠르게 탐색할 방법이 필요합니다.
  • 크기 집합에 따라 별도의 가용 리스트를 처리하면 (segregated free list) 보다 두 점수를 높일 수 있습니다. 이 방법은 나중에 별도의 글로 적어볼게요!
profile
방법이있지
뭔가 만드는 걸 좋아하는 개발자 지망생입니다. 프로야구단 LG 트윈스를 응원하고 있습니다.
이전 포스트

[C] 분할 컴파일 / 헤더 중복문제 해결

다음 포스트

[0702 발표] 푸터 생략하고 4바이트 아끼기

3개의 댓글

comment-user-thumbnail
개굴이
2025년 8월 22일

안녕하세요!! 이제 7주차 말록구현하고있는 10기입니다!!
선배님께 궁금한게 있는데
혹시 이거 직접 구현 하신건가요?
realloc 같은 경우
저는 도저히 어떻게 해야할지 모르겠어서 따라치면서 이해해보려고 하는데 괜찮을까요 ㅠㅠ..

1개의 답글