[TIL] 5주차 - (2) : C 동적 메모리 할당 코드 분석 및 구동 방식 파악

오늘은 malloc() 함수를 실제 구현해 보는 과정을 진행하기 위한 초석이다.

 

 

더 성능 좋은 malloc으로 구현하기 위해 책에 구현된 코드의 define 문과 함수를 전부 분석하고,

 

책의 어떤 방식을 채택하여 구현되어 있는지 확인해본 뒤 어떻게 개선할 수 있을지 여부를 판단하겠다.

 

---

 

 

CS:APP 9.9 코드 예제 해석

 

먼저 코드의 내부 시스템 코드인 memlib.c 와 Define 문으로 정의된 코드부터 파악해보자

 

 

 - memlib.c

 

해당 파일은 시스템 자원인 heap의 시작 pointer , heap이 현재까지 할당된 end pointer , heap의 최대 끝 end pointer를 기억하고 있다.

 

해당 데이터는 각각 mem_heap , mem_brk , mem_max_addr에 저장되어 있고,

해당 포인터는 직접 요청이 불가능하게 static으로 선언되어 memlib 코드 내부에서만 해당 값을 참조 가능하다.

 

 

/* single word (4) or double word (8) alignment */
#define WSIZE 4
#define DSIZE 8
#define CHUNKSIZE (1<<12) // Extend heap by this amount (bytes)

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

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

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

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

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

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

 

 

- #define

 

먼저 간단한 상수 정의는 그림을 참조하는 것으로 하고,

 

나머지를 간단하게 설명하면

 

 

PACK은 size 데이터와 할당 상태를 header 블록이나 footer 블록에 저장할 데이터를 생성한다.

 -> 이는 PUT과 함께 사용하여 header과 footer에 저장된다.

 

GET은 포인터를 인자로 받아 해당 위치의 값을 받는데, 이는 보통 header나 footer 블록의 데이터를 추출하여 해당 블록의 크기와 할당여부를 파악할 때 사용한다.

 

PUT은 PACK으로 생성한 header와 footer 값을 각각 header위치와 footer 위치에 저장할 때 사용한다.

 

GET_SIZE는 header과 footer의 포인터 위치를 통해 해당 블록의 사이즈를 반환해준다.

 

GET_ALLOC는 header와 footer의 포인터 위치를 통해 해당 블록의 할당 여부를 반환한다.

이때, 할당된 상태이면 1(True) , 반환 상태라면 0(False) 라는 점을 기억해야 한다.

 

HDRP는 bp를 통해 해당 블록의 header 위치 포인터를 반환한다.

 

FTRP는 bp를 통해 header의 위치를 HDRP로 받은 뒤 HDRP을 통해 size 값을 받아 연산하여 footer로 점프하여 footer의 위치를 반환한다.

 

NEXT_BLKP는 bp에서 한칸 이전인 header로 간 뒤, 다음 블록의 bp로 점프하여, 결과적으로 다음 블록의 bp를 반환한다.

 

PREV_BLKP는 bp에서 두칸 이전인 이전 블록의 footer로 간 뒤, 해당 블록의 크기를 받아 연산하여 점프 한 뒤, 이전 블록의 bp를 반환한다.

 

! 'bp' 의 위치는 어디?

 

HDRP를 이해하기 전에 bp의 위치에 대해 이해해보자.

 

결론부터 말하자면,  bp는 블록을 할당 받았을 때, header의 다음 위치이다.

 

memlib.c의 코드로부터 전달받는 포인터로 시작되는 bp는 mm.c에서 모두 header와 footer의 위치를 판단할 수 있는 중요한 포인터이다.

 

잘 이해가 되지 않는다면 위 그림의 필기를 통해 확인해보자.

 

---

 

 

위 설명을 통해 동적 할당을 주도하여 포인터를 직접 옮겨주는 memlib.c 코드의 구성과

mm.c에서 사용할 간단히 정리한 define 문을 모두 이해했다.

 

 

이제 mm.c에 들어가는 교재 속 코드를 분석해 보자.

 

 

해당 필기를 보는것이 각각의 함수를 전체적으로 이해하는데 도움 된다.

 

---

 

 

- int mm_init(void)

 

static void *heap_listp;

int mm_init(void)
{
    if((heap_listp = mem_sbrk(4*WSIZE)) == (void *)-1){
        return -1;
    }
    PUT(heap_listp,0);
    PUT(heap_listp + (1*WSIZE) , PACK(DSIZE, 1));
    PUT(heap_listp + (2*WSIZE) , PACK(DSIZE, 1));
    PUT(heap_listp + (3*WSIZE) , PACK(0, 1));
    heap_listp += (2*WSIZE);

    if(extend_heap(CHUNKSIZE/WSIZE) == NULL){
        return -1;
    }
    return 0;
}

 

init 함수는 동적할당을 위해 틀을 구색하는 코드로 이해하면 된다.

 

memlib.c 코드의 함수 mem_sbrk를 통해 4개의 블록을 할당받는다.

 

할당받은 블록의 제일 처음 블록은 비워 두고, 두번째 블록은 프롤로그 header , 세번째 블록은 프롤로그 footer , 네번째 블록은 chunk block 단위의 끝을 의미하는 에필로그 header로 만든다.

 

 

사용자가 할당받는 동적 할당 메모리는 프롤로그 footer와 에필로그 header 사이에서 늘어나는 chunk heap 메모리 공간이며,

 

뒤에 나올 extend_heap() 함수로 적절히 큰 단위인 chunksize로 heap을 크게 한번 할당 해 놓은 뒤 사용하고

이후 chunk에 할당하지 못하는 데이터를 요청받으면 chunksize의 heap을 재요청하여 heap을 늘리는 방식이다.

 

 

이때, 이후의 함수에서 사용하는 bp를 잘 이해하기 위해 기억해야 할 중요한 부분이 있다.

 

지금 설명하고 있는 init() 함수가 실행되었을 때, memlib.c 소스파일 내의 mem_sbrk() 함수가 호출되면서

static 변수인 mem_brk가 어떻게 기억되어 있을지 생각해보아야 한다.

 

앞으로 사용자가 동적할당을 요청할 때 마다 mem_sbrk()가 실행될 때,

memlib에서 동적 메모리를 할당해주는 포인터를 return하면서 mem_brk 포인터 변수는 할당받은 메모리 블록의 다음 블록 'bp'를 가리키도록 설정된다.

 

그렇다면 왜 header 위치의 포인터를 건너 뛴 bp로 설정될까?

 

이는 처음 init() 함수를 실행했을 때, mem_brk가 처음 동적 할당 될 블록의 bp 위치를 기억하고 있도록 구현되어 있기 때문이다.

 

init() 함수가 4개의 W 블록을 요청하면서 mem_brk는 에필로그 header의 다음 블록의 주소를 가지고 있다.

잘 생각해보면, init() 내에서 처음 할당되는 chunk block의 bp를 가리키고 있었다는 것을 알 수 있다.

 

 

이후의 함수에서 확인하겠지만 동적 할당 시,

 

bp위치를 통해 그 이전 블록에 header 정보를 삽입하고, header에서 footer 위치로 점프하여 footer 정보를 삽입한다.

 

 

 

 

- static void *extend_heap(size_t words)

 

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

    size = (words % 2) ? (words+1) * WSIZE : words * WSIZE;
    if ((long)(bp = mem_sbrk(size)) == -1){
        return NULL;
    }

    PUT(HDRP(bp), PACK(size,0));
    PUT(FTRP(bp), PACK(size,0));
    PUT(HDRP(NEXT_BLKP(bp)) , PACK(0,1));

    return coalesce(bp);

}

 

해당 함수는 init() 안에서 사용된 chunk 단위의 heap을 할당하는 함수이다.

 

header와 footer를 chunk heap 공간의 양 끝에 두고, malloc 선언 요청이 들어오면 그 내부의 공간을 끊어서 사용한다.

 

 

 

 

- void mm_free(void *bp)

 

void mm_free(void *bp)
{
    size_t size = GET_SIZE(HDRP(bp));

    PUT(HDRP(bp) , PACK(size,0));
    PUT(FTRP(bp) , PACK(size,0));
    coalesce(bp);
}

 

동적 할당된 블록의 bp를 통해 해당 메모리를 반환하는 함수이다.

 

이는 bp를 통해 해당 블럭의 header와 footer의 사이즈는 그대로 둔 뒤 할당 여부를 0으로 바꾸어 가용상태로 만든다.

 

그 이후 뒤에 설명할 가용 블록들을 연결하는 coalesce(bp) 함수를 호출한다.

 

 

- static void *coalesce(void *bp)

 

static void *coalesce(void *bp){
    size_t prev_alloc = GET_ALLOC(FTRP(PREV_BLKP(bp)));
    size_t next_alloc = GET_ALLOC(HDRP(NEXT_BLKP(bp)));
    size_t size = GET_SIZE(HDRP(bp));

    if (prev_alloc && next_alloc) {
        return bp;
    }

    else if(prev_alloc && !next_alloc){
        size += GET_SIZE(HDRP(NEXT_BLKP(bp)));
        PUT(HDRP(bp), PACK(size, 0));
        PUT(FTRP(bp), PACK(size, 0));
    }

    else if(!prev_alloc && next_alloc){
        size += GET_SIZE(HDRP(PREV_BLKP(bp)));
        PUT(FTRP(bp) , PACK(size,0));
        PUT(HDRP(PREV_BLKP(bp)) , PACK(size, 0));
        bp = PREV_BLKP(bp);
    }

    else {
        size += GET_SIZE(HDRP(PREV_BLKP(bp))) + GET_SIZE(FTRP(NEXT_BLKP(bp)));
        PUT(HDRP(PREV_BLKP(bp)) , PACK(size,0));
        PUT(FTRP(NEXT_BLKP(bp)) , PACK(size,0));
        bp = PREV_BLKP(bp);
    }

    return bp;
}

 

해당 함수는 현재 free 함수를 통해 반환되었거나 chunk size의 heap을 재할당할 때,

양 옆의 가용 블록을 하나로 합치기 위해 사용한다.

 

이때, 현재 bp위치로부터 이전 블록의 header나 footer로 이동하여 할당 여부를 확인한 뒤 가용 블록의 크기를 재 설정하여 병합을 진행한다.

 

이는 오류 단편화(False fragmentation)를 예방하기 위한 작업으로, 현재 코드에서는 즉시 연결법을 사용하고 있다.

 

 

 

 

- void *mm_malloc(size_t size)

 

void *mm_malloc(size_t size)
{

    size_t asize;
    size_t extendsize;
    char *bp;

    if (size == 0){
        return NULL;
    }

    if (size <= DSIZE){
        asize = 2*DSIZE;
    }
    else{
        asize = DSIZE * ((size+(DSIZE) + (DSIZE-1)) / DSIZE);
    }

    if ((bp = find_fit(asize)) != NULL){
        place(bp, asize);
        return bp;
    }

    extendsize = MAX(asize, CHUNKSIZE);
    if ((bp = extend_heap(extendsize/WSIZE)) == NULL){
        return NULL;
    }
    place(bp, asize);
    return bp;
}

 

실제 사용자가 요청하는 동적 메모리 할당 함수이다.

 

내부에서 요청한 size 크기에 맞추되 더블워드 크기의 배수로 할당해주는 로직이 구현되어 있다.

 

이후 find_fit()함수를 통해 해당 사이즈의 빈 블록이 있는지 확인한 뒤

빈 블록이 있다면 place()함수를 통해 빈 블록을 할당된 블록으로 변경하는 과정을 수행한다.

 

 

 

 

- static void *find_fit(size_t asize)

 

static void *find_fit(size_t asize){

    void *bp;

    for(bp = heap_listp; GET_SIZE(HDRP(bp)) > 0; bp = NEXT_BLKP(bp)){
        if (!GET_ALLOC(HDRP(bp)) && (asize <= GET_SIZE(HDRP(bp)))){
            return bp;
        }
    }

    return NULL;
}

 

malloc 함수에서 호출한 빈 블록을 탐색하는 함수이다.

 

처음 init 시에 저장해 놓은 heap_listp 포인터를 시작점으로 각 헤더를 조사하여 해당 사이즈의 빈 블록이 있는지 탐색한다.

 

이는 heap의 처음부터 일방향으로 탐색하고 있기에 교재의 코드는 first-fit 방식을 채택했음을 알 수 있다.

 

 

 

- static void place(void *bp , size_t asize)

 

 

static void place(void *bp , size_t asize){
    size_t csize = GET_SIZE(HDRP(bp));

    if((csize - asize) >= (2*DSIZE)) {
        PUT(HDRP(bp) , PACK(asize , 1));
        PUT(FTRP(bp) , PACK(asize , 1));
        bp = NEXT_BLKP(bp);
        PUT(HDRP(bp) , PACK(csize - asize , 0));
        PUT(FTRP(bp) , PACK(csize-asize , 0));
    }
    else{
        PUT(HDRP(bp) , PACK(csize, 1));
        PUT(FTRP(bp) , PACK(csize, 1));
    }
}

 

마지막 함수인 place()는 사용자가 원하는 크기의 빈 블록을 탐색에 성공한 뒤, 해당 블록을 할당해주기 위한 작업이다.

 

해당 블록은 할당된 것으로 표시 (헤더와 푸터에 alloc = 1)하고,

만약 할당하고 남은 블럭들이 최소 더블워드 블록 크기보다 크다면 해당 블록을 잘라내 header를 생성하여 남은 블록 자원이 빈 상태임을 표시해준다.

 

만약 최소 더블워드 블록 크기보다 작다면, 그냥 남은 블록까지 할당해준 블록에 추가로 할당 한 것으로 표시한다.

 

---

 

마무리

 

해당 함수와 코드가 어떤 방식을 채택하여 구현되어 있는지 확인했다.

 

해당 함수를 구현한 동적 메모리 할당 코드는 69/100점 이다.

 

 

오늘 남은 시간에 개선할 여부를 정리하여 구현 한 뒤 내일은 개선한 코드에 대해 정리하겠다.