정글[Week_07]: malloc(동적 할당기) 직접 구현 후기

매주 WIL을 작성을 한다. 사실 작성을 할 때마다, 어떠한 주제를 다뤄야 할 지 항상 고민을 했었다. 매 주 다루는 내용이 하나하나 소중하고, 놓치고 싶지 않고 싶은 마음이 원인이 아니었을까 싶다. 매 주 수요코딩회 내용을 적었지만, 이번에는 방향을 바꿔 malloc_lab에 대해 학습하고 구현한 내용을 담고자 한다. 동적 할당.. 이른바 malloc은 CS지식, 향후 pintOS와 같은 운영체제 구현에 있어서 밑걸음이 된다고 생각하여 선정을 하였다.

 

 

동적 할당기(Dynamic Allocator)란?

컴퓨터의 자원은 한정되어 있다. 따라서 프로그램이 돌아가기 위해서는 메모리를 할당하고, 필요없어질 경우 이를 해제하는 과정을 반복해야 한다. 그런데, 이 할당 과정은 동적(Dynamic)과 정적(Static)할당으로 나뉜다. 무엇을 기준으로 할까? 바로 컴파일을 기준으로 하여 나눈다. 모든 언어가 그렇지 않지만, c의 경우 프로그램이 실행될 때, 컴파일 과정을 거쳐 전채 목적 파일(Object file)을 만든다.

목적 파일은 프로그램의 대략적인 설계도를 가지고 있고, 이에 맞게 메모리를 할당한다. 예를 들어 int arr[100]; 라는 변수가 있다고 가정해보자. 이는 컴파일 과정에서 실제 100개의 int 배열을 저장하는 공간을 미리 확보해 놓는다. 그리고 이는 프로그램이 종료되기 전 까지 변하지 않으므로 정적 할당이라고 한다.

반대로 동적 할당은 프로그램이 돌아가는 런타임 동안 시시각각 할당을 한다. 문제는 python과 같은 고수준 언어는 힙 영역에서 알아서 할당과 해제가 일어난다. 그러나 c언어와 같은 저수준 언어는 할당/해제를 하는 작업을 직접 코드에 명시해야 한다. 대표적인 할당 함수로는 malloc, 해제로는 free가 있다. 이 둘을 그저 사용하는 것이 아닌, 직접 구현하는 것이 이번 프로젝트이다.

 

 

malloc 구현을 위한 기본 함수들

malloc 기능을 구현하기 위해서 어떤 함수를 구현을 해야 하는지, 학습을 해야 한다. CSPP 서적에는 구현을 위한 표준화된 함수들이 있었고, 당장 내가 내키는 데로 구현을 하기 보다는 규칙을 따라 학습하기로 했다. 구연해야 할 필수 함수 8개를 표로 정리하자면 다음과 같다:

함수명	기능 설명
mm_init(void)	초기화 함수. 메모리 할당을 위한 기본 셋팅(패딩, 프롤로그, 에필로그) 담당.
mm_malloc(size)	해당 size의 메모리를 요청하면 이를 힙에 할당하는 함수.  호출되는 함수: find_fit, place, extend_heap
mm_free(*bp)	특정 주소값(*bp)에 해당되는 블록을 해제. 호출되는 함수: coalesce
mm_realloc(*bp, size)	특정 주소값(*bp)의 블록의 크기를 size만큼 변경하여 다른 장소에 재할당 하는 작업.
find_fit(size)	해당 size의 메모리를 넣기 위해 빈 블록을 탐색하는 함수.
coalesce(*bp)	특정 주소값(*bp)의 메모리를 해제했을 때, 인접 free 블록과 병합하는 함수.
extend_heap(size)	힙을 확장하는 함수.
place(*bp, size)	빈 *bp 메모리에 size 만큼 할당할 시 나머지 여분 free 공간 조율.

처음 본다면 상당히 난해하게 느껴질 수 있다. 이 함수를 하나하나 살펴보기 전에, 왜 이렇게 분리하고 실행되는지 대략적으로 파악을 해보고자 한다.

 

 

메모리는 블록 단위로 계산된다

메모리 블록

메모리를 할당하고 해제를 하려면 각 영역을 나누고 해제를 해야 한다. 위의 그림은 한 블록의 예시이다. 일반적으로 block에는 앞뒤로 헤더와 푸터가 붙는데, 이는 블록의 경계값을 표시하고, 해당 블록이 할당되었는지 비워져 있는지 (마지막 3비트)를 통해 표시한다. 보통 마지막 비트가 1이면 할당, 비워져 있으면 비워져 있음을 나타낸다. Payload는 실제 데이터가 저장되는 영역이며, padding은 배수를 맞추기 위해 추가 여분을 넣은 것이다. 

 

 

다양한 메모리 할당 방법

이렇게 양 끝에 붙은 헤더와 푸터를 이용하여 다음 메모리를 탐색할 수 있다. header나 footer에 특정 값이 저장되어 있다고 가정해볼 경우, header만 읽음으로써 다음 작업을 수월하게 처리하는 방법을 생각해보자.

 

implicit allocation(묵시적 할당)

묵시적 할당

묵시적 할당은 단어에서 유추하듯, 직접적인 표시를 하지 않고 인접 블록은 추적하는 방법이다. 각 헤더에 해당 블록의 size와 할당 유무를 표시한다고 가정해보자. 다음 블록으로 넘어갈 때, 헤더의 size 만큼 점핑을 하면 다음 헤더로 갈 수가 있다. 헤더에서 헤더로 점핑하면서 free인 블록을 찾아 메모리를 넣는 방법이 implicit(묵시적)으로 나는 이해를 하였다.

// implicit 구현: 시작부터 ==> 에필로그 헤더까지 순회
static void *find_fit(size_t put_size){
    void *bp; 

    for(bp = heap_listp; GET_SIZE(HDRP(bp)) > 0; bp = (char *)bp + GET_SIZE(HDRP(bp))){  
        size_t header_value = *(size_t *)HDRP(bp); 
        int is_allocated = header_value & 0x1; 
        if(!is_allocated && (put_size <= GET_SIZE(HDRP(bp)))){ 
            return bp; 
        }
    }

    return (void *)-1; 
}

코드는 다음과 같이 작성이 가능하다. 위에 기술된 함수는 find_fit으로for문을 살펴보면 힙의 시작점(heap_listp)부터 끝(epilogue) 까지 순회하는 것임을 알 수가 있다. 매 블럭의 size 만큼 점핑을 하면서, 요구하는 put_size이상인 크기를 가진 free 블록을 찾으면 해당 블록의 주소값(payload)를 반환하는 로직이 구성되어 있다.

 

explicit allocation(명시적 할당)
명시적 할당은, 위의 implicit에서 걸리는 번거로움이 다소 해결이 된다는 장점이 있다. 묵시적 할당은 매 블록의 size 마다 점핑을 해야 하므로 일일이 (해당 블록의 free 유무 상관 없이) 확인을 해야 한다. 명시적 할당은 free 블록의 헤더에 다음 free 블록의 주소값을 저장하는 방식을 통해서 free 블록 끼리만 점핑이 가능하도록 구현하였다.

명시적 할당

static void new_connect(void *bp); // explicit: free간 연결 함수
static void disconnect(void *bp); // explicit: 해당 free 블럭 끊고 => 앞뒤로 연결하는 함수

// implicit 통합 테스트: Perf index = 46 (util) + 16 (thru) = 62/100
// explicit 통합 테스트: Perf index = 44 (util) + 40 (thru) = 84/100

명시적 할당을 하기 위해선 추가적인 함수 구현이 필요하다. free 블록의 payload에 이전/이후 블록의 주소를 할당하여 연결하는 new_connect함수, 그리고 free블록이 해제가 되었을 경우, 이를 빼고, 앞뒤 블록을 연결하는 disconnect 함수를 추가 구현하였다. 그렇다. explicit는 free메모리 간의 일종의 연결 리스트와 같이 상호 간의 주소를... 현재는 빈 공간인 payload에 임시로 넣는 것이다.

 

seglist allocation

seglist 할당

seglist 할당은 명시적 할당에서 좀 더 기능을 추가하는 방식으로 구현이 가능하다. 명시적 할당에서는 모든 free메모리를 모두 하나의 연결망?에서 하나의 줄 처럼 연결을 하였다. 이렇게 할 경우, 원하는 자리를 찾기 위해서, 최악의 경우 모든 free 블록을 탐색해야 할 수 있다. seglist는 연결망을 size 별로 나눠서 이러한 시간 복잡도를 해결한다. 위의 그림을 보면, free한 메모리의 크기에 따라 분류를 하고, 유사한 size의 블록들만 서로 연결을 한 것을 볼 수 있다.

    int list = 0;
    size_t class_size = size; // class 계산용

    while((list < LISTLIMIT - 1) && (class_size > 1)){
        class_size >>= 1; // 5: 63- ,6: 127-, 7: 255-, .... , 15: 65535-, 16: 65536>
        list++; // 인덱스 구해짐
    }

유사한 size의 연결망 또한 이 망에 접근하기 위한 root node가 존재한다. 해당 root node를 가리키는 포인터 주소값을 seglist라는 포인터 리스트에 저장을 한다. 리스트에는 index를 통해 root node에 접근을 한다. 이 index를 구하는 방법은 비교적 수월하다. 위의 코드를 통해, list = 0 이라는 인덱스 값을 초기화를 하고, class_size를 바탕으로 비트 연산을 하여 list 인덱스를 구할 수 있음을 알 수 있다.

 

 

그 외에 중요한 함수들

그 외에 내가 집중한 함수는 다음과 같다:

coalesce(*bp):
free 블록 간 병합을 하는 함수이다. 경우의 수는 총 4가지(본인만 free, 앞만 ", 뒷만 ", 양쪽 다 free)이다. explicit 단계에 진입하면서 수정해야 할 내용이 많아진다. 왜냐하면 free 블록을 병합을 하면, free 블록을 연결하는 망 또한 상당한 손질이 필요하기 때문이다.

realloc(*bp, size):
기존 메모리를 확장하여 재할당 하는 함수이다. 경우의 수가 상당히 많기 때문에, 일일이 구현하다 보면 스파게티 코드가 되기 쉽다. 기본적으로 바로 mm_malloc을 다시 호출하여 탐색을 하도록 구성이 되어있다. 그러나 이러한 경우, 놓치는 경우가 상딩히 많은데.... 현재 블록에서 옆에 free가 있을 때, 미리 확장 후 재할당을 바로 하거나.. heap의 맨 끝에 있는 메모리의 경우 heap을 나머지 여분만 확장하는 경우 등 다양하다. 아래는 테스트 결과이며, 힙 말단 확장 로직 추가만으로 util(메모리 유용력)이 상당수 개선됨이 나타난다.

// seglist 통합 테스트: Perf index = 47 (util) + 40 (thru) = 87/100
// realloc 힙 말단 확장: Perf index = 52 (util) + 40 (thru) = 92/100

 

 

끊임없이 방향을 탐색하며 공부하기

맨 처음 구현 과제가 주어졌을 때, 어디서 파악을 하고 스타트를 끊어야 할지 막막함을 느꼈었다. CSAPP 챕터 9에서 각 샘플 함수와 설명이 기술되어 있으나, 이것을 그대로 복붙하여 어떻게든 구동이 된다고 해도 내 것이 되지 못한다는 단점이 있었다. 나는 여기서 톱-다운 방식의 학습법을 도입하였다. 먼저 소스 코드를 살펴보고, 하나하나 디버깅 하면서 어떠한 인자를 받고 처리를 하는지 printf를 통해 확인을 하였다. 이를 통해서 기본으로 구현된 mm_init, mm_malloc, mm_free, mm_realloc .. mm_sbrk를 파악하였다. 이후 각 함수가 어떻게 꼬리에 꼬리는 무는지 상세한 지도를 머릿속에 그려나갔다.

 

단계적으로 어려움을 돌파하기
학습가이드에서 또한 implicit → explicit → seglist로 나아가라는 권유가 있었다. 나름의 반항심?이 발동하여, 맨 마지막 부터 해볼까? 생각하였지만, 구현을 하면서 이것이 단계적으로 개념을 응용하여 탐색과 메모리 자원을 더 절약하는 방법임을 깨닫고 가이드를 충실하게 따랐다.

Implicit는 어떻게 보면 완전탐색과 같이 원하는 블록이 나올 때 까지 1번부터 순회를 한다. 여기서 explict는 payload에 포인터를 추가하여, 탐색할 블록 중 할당된 블록은 제외하였다. 여기서 seglist는 포인터 list 배열을 추가하여, free 블록을 사이즈에 맞춰 분리 작업을 추가한 것이다.

아쉬운 점은 있다. realloc을 인접 next에만 확장 가능하도록 로직을 작성하고 prev는 난해하게 느껴져서 거기까지 도달하지 못했다는 점, 할당 블록의 footer를 없애도 header의 2번째 바이트에 이전 블록의 정보를 저장하는 방식을 도입하였지만... 생각보다 수치가 개선되지 못했다는 점이다. 이러한 점들이 기억에 남으나, 이 아쉬움이 다음에는 성취로 이어지는 원동력이 되어줄 것이라 믿는다.