Implicit allocator 구현

솔다·2022년 12월 7일
0

크래프톤 정글을 진행하며 이번에는 Implicit allocator를 구현했다. 아래에 코드를 보며 설명할 것이다.


/* define add */
#define WSIZE   4   // 32bit -> word
#define DSIZE   8   // 32bit -> double word
#define CHUNKSIZE   (1<<12) // 32bit -> basic heap size

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

#define PACK(size, alloc)   ((size) | (alloc))  // header & footer data

#define GET(p)  (*(unsigned int *)(p))  // read word at address p
#define PUT(p, val)   (*(unsigned int *)(p) = (val))    // write word at address p

#define GET_SIZE(p) (GET(p) & ~0x7) // read block size
#define GET_ALLOC(p) (GET(p) & 0x1) // read block allocated

#define HDRP(bp)    ((char *)(bp) - WSIZE)  // header address
#define FTRP(bp)    ((char *)(bp) + GET_SIZE(HDRP(bp)) - DSIZE) // footer address

#define NEXT_BLKP(bp)   ((char *)(bp) + GET_SIZE(((char *)(bp) - WSIZE)))   // next bp address
#define PREV_BLKP(bp)   ((char *)(bp) - GET_SIZE(((char *)(bp) - DSIZE)))   // pre bp address

위의 코드는 CS 책에 나와있는 가용 리스트 조작을 위한 기본 상수 및 매크로 정의이다. 가용 리스트 조작을 위해서 다양한 기능을 구현하는데 이는 위와 같이 기본적인 매크로를 define 해놓는 것으로 매우 유용하게 이용해서 코드를 쉽게 짤 수 있게 해준다.

다음은 초기화 함수이다.


/* forward declaration function */
static void *extend_heap(size_t words);
static void *coalesce(void *bp);
static void *find_fit(size_t asize);
static void place(void *bp, size_t asize);
static char *heap_listp;
static char *last_bp;

/* 
 * mm_init - initialize the malloc package.
 */

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);
    // last_bp = (char *)heap_listp;

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

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);
}

가장 처음 부분은 함수정의 및 전역변수 설정이다. 이 코드에서는 first fit 방식과 next fit방식을 모두 구현했기 때문에 last_bp라는 포인터 변수가 하나 있다.

init을 하게 되면 가장 처음에 header, footer, epilogue를 생성한다. 그리고 heap_listp는 가용리스트의 시작부분을 정확하게 가리키게 된다.

또한 extend heap을 통해서 최초에 한번 영역을 확장하게 된다. extend_heap은 두 가지 경우에 실행된다. 1) 가장 처음에 코드를 실행시킬 때 2) allocating 하는 과정에서 메모리가 부족하여 추가할 때

처음 코드를 실행시키면서 확장된 영역만큼 다시 header와 footer를 가용 블록이라는 정보를 담아 놓게된다.

이 과정에서 coalescing도 실시하게 되는데 이에 관한 코드는 아래에서 설명하겠다.

static void *coalesce(void *bp){
    size_t prev_alloc = GET_ALLOC(HDRP(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){

        last_bp = (char *)bp;
        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(HDRP(PREV_BLKP(bp)), PACK(size, 0));
        PUT(FTRP(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);

    }
    last_bp = (char *)bp;
    return bp;
}

coalescing은 조금 복잡한데, 지금 포인터가 있는 곳을 기준으로 4가지 경우로 나누어서 실행이 된다. 앞과 뒤의 블록들이 가용블록인지 아닌지에 따라서 4가지의 경우가 나오는 것에 따라 블록을 합치게 된다. 이 과정은 처음에 define 해 두었던 매크로를 이용해서 header와 footer의 정보를 수정해주는 것으로 쉽게 바꿀 수 있다.

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);

    /* Search the free list for a fit */
    if ((bp = find_fit(asize)) != NULL){
        place(bp, asize);
        last_bp = NEXT_BLKP(bp);  /*next fit을 위한 bp 저장*/
        return bp;
    }
    
    /*No fit found. Get more memory and place the block */
    extendsize = MAX(asize, CHUNKSIZE);
    if ((bp = extend_heap(extendsize/WSIZE)) == NULL){
        return NULL;
    }
    place(bp, asize);
    last_bp = NEXT_BLKP(bp);  /*next fit을 위한 bp 저장*/
    return bp;

}

malloc 함수이다. 현재 위의 코드는 next fit을 기준으로 작성되었기 때문에, last_bp값을 최신화하여 가용블록 검색시에 활용한다. 데이터를 일정 사이즈로 넣을 때는, 더블블록 경계 기준을 만족시키기 위해 일정 사이즈로 조정한 뒤에 블록에 할당하는 함수 place를 호출한다.

static void *find_fit(size_t asize){
    // /* First fit */
    // void *bp;

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

    // return NULL;

    /* Next fit */
    void *bp;

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

    return NULL;

}

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

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

위의 함수는 가용블록 검색을 위한 search함수, 그리고 실질적으로 header와 footer에 정보를 넣어주는 place 함수이다. First Fit 방식은 단순하게 heap_listp를 기준으로 매번 검색을 시작하는 방식임을 확인할 수 있고, Next Fit 방식은 마지막으로 참조했던 포인터인 last_bp를 기준으로 탐색하는 것을 볼 수 있다.

Next Fit 방식으로 되어있는 함수를 뜯어보면 두 개의 for문으로 구성되어 있는데, 이는 현재 위치부터 검색을 끝까지 한 이후(epilogue를 만나는 시점) 까지 탐색을 하고, 조건에 맞는 블록을 찾으면 리턴, 못 찾으면 다시 처음부터 last_bp 까지 다시 for문을 통해 탐색을 실시한다. 조건에 맞는 녀석을 찾아서 return하면 이 포인터를 기준으로 place 함수를 실행하게 된다.

place함수에서는 할당하고 나서 패딩 영역이 최소크기의 데이터를 할당할 수 있는 경우에는 split 해서 나누어 주는 경우와 그냥 할당하는 경우로 나누어서 작성되었다.


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

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

/*
 * mm_realloc - Implemented simply in terms of mm_malloc and mm_free
 */
void *mm_realloc(void *ptr, size_t size)
{
    size_t old_size = GET_SIZE(HDRP(ptr));
    size_t new_size = size + (2 * WSIZE);

    if (new_size <= old_size)
        return ptr;
    else
    {
        size_t next_alloc = GET_ALLOC(HDRP(NEXT_BLKP(ptr)));
        size_t current_size = old_size + GET_SIZE(HDRP(NEXT_BLKP(ptr)));

        if (!next_alloc && size <= current_size)
        {
            PUT(HDRP(ptr), PACK(current_size, 1));
            PUT(FTRP(ptr), PACK(current_size, 1));
            return ptr;
        }
        void *new_bp = mm_malloc(new_size);
        memcpy(new_bp, ptr, new_size);
        mm_free(ptr);
        return new_bp;
    }
}

남은 두 함수는 free함수와 realloc 함수이다. free함수는 말그대로 데이터를 없애고 가용블록으로 바꾸어 주는 경우이다. 이 경우 가용블록이 생성되므로 앞과 뒤에 가용블록이 있는경우 하나의 블록으로 합쳐주어야 메모리를 효율적으로 할당할 수 있다. 그래서 Free를 하면서 coalesce 함수를 호출해준다.

realloc 함수는 말그대로 데이터를 재할당하는 함수이다. 원하는 위치에 있는 포인터의 값을 다른 포인터 위치에, 값을 복제하는 함수이다. 이 함수를 수행할 때, 현재 블록의 크기와 새로 할당하기를 원하는 크기를 고려하여서 데이터를 이동 or 이동X 로 선택하여 실행되도록 코드를 구성하였다.

또한, 데이터 주소가 변경된 경우에는, 이전의 주소에는 새로운 데이터를 넣을 수 있는 가용블록이 되어야 하기에 Free 함수를 호출해 준다. memcpy 함수는 새로운 포인터 위치에 현재 포인터 위치에서 new_size 만큼의 데이터를 그대로 복제해 주는 함수를 의미한다.


아쉽게도 explicit 방식으로는 구현해보지 못했지만, 나중에 시간이 있다면 시도해보고 싶은 생각이 드는 과제였다. malloc을 구현하면서 가상메모리에 대해서 공부했지만 여전히 헷갈리는 개념들이 있다. 이런 개념들을 정리하기 단순히 malloc 구현 코드 외에도 별도로 개념을 정리해보고자 한다.

0개의 댓글