[Malloc Lab] Implicit List

간접 리스트 방식으로 malloc, free 를 구현해보도록 하겠습니다.

 

간접 리스트 방식으로 구현하기에 앞서 Malloc / Free 를 구현할 때 유용한 매크로 변수, 매크로 함수, 메소드 들에 대한 설명을 첨부합니다.

 

 

먼저 mm_implicit.c 의 mm_init 메소드를 구현하겠습니다. mm_init 메소드는 동적 메모리 할당을 하기 위한 초기 힙 구조를 생성하는 메소드입니다.

/*
 * Initialize: return -1 on error, 0 on success.
 */
int mm_init(void) {
    if ( (heap_listp = mem_sbrk(4*WSIZE)) == -1 ) // 초기 empty heap 설정
        return -1; // heap_listp = 새로 생성되는 heap 영역의 시작 주소

    PUT(heap_listp, 0); // heap의 시작부분 할당
    PUT(heap_listp + WSIZE, PACK(OVERHEAD, 1)); // prologue header block
    PUT(heap_listp + DSIZE, PACK(OVERHEAD, 1)); // prologue footer block
    PUT(heap_listp+WSIZE+DSIZE, PACK(0, 1)); // epilogue header block
    heap_listp += DSIZE; // heap_listp를 footer block에 locate

    if (extend_heap(CHUNKSIZE / WSIZE) == NULL) { // CHUNKSIZE Bytes 의 free block 을 생성. 초기 가용블럭을 생성합니다.
        return -1;
    }
    
    return 0;
}

mem_sbrk 함수를 통해 힙 영역의 크기를 키워줍니다. mem_sbrk 는 brk 포인터를 증가시킴으로써 힙 영역의 크기를 키우고 증가시키기 전 brk 포인터의 위치를 반환합니다. mem_sbrk 코드는 memlib.h 에 내장되어 있습니다. 코드 내용은 다음과 같습니다. epilogue 블럭의 사이즈는 특이하게 0임에 유의합시다.

 

mem_sbrk 의 코드

 

heap_listp 에 mem_sbrk를 통해 워드 4개만큼 힙을 증가시키고 만약 힙 영역을 증가시킬 수 없다면 -1을 반환합니다.

 

put 을 이용해 Root Block 에 0을 입력하고, 그 다음 워드에 prologue header block, 그 다음 워드에 prologue footer block, 그 다음 워드에 epilogue block 을 정보와 함께 입력하고 heap_listp 를 prologue footer block 에 위치시키고, CHUNKSIZE 바이트만큼 증가시킵니다.

 

이번엔 Implicit List 방식을 이용해 malloc 함수를 구현해보도록 하겠습니다. malloc 함수의 소스코드는 다음과 같습니다.

/*
 * malloc
 */
void *malloc (size_t size) {
    size_t asize;
    size_t extendsize;
    char *bp;

    if (size < DSIZE) { //malloc 의 size 가 double words 보다 작을 경우
        asize = DSIZE + OVERHEAD;
    } else {
        asize = DSIZE * ( (size + 2*DSIZE - 1) / DSIZE );
    }

    if ( (bp = find_fit(asize)) != NULL) {
        place((void *)bp, asize);
        return (void *)bp;
    } else { // find_fit 을 통해 가용블럭을 찾지 못한 경우, 힙을 증가시킵니다.
        extendsize = MAX(asize,CHUNKSIZE);
        if ( (bp = extend_heap(extendsize)) != NULL) { // CHUNKSIZE BYTES의 heap을 새로 생성합니다. 
            place((void *)bp, asize);
            return (void *)bp;
        }
    }
    return NULL;
}

asize 는 adjusted Size 로, 실제 payload 를 저장할 공간 + header 와 footer, 그리고 Even Words Align을 위한 padding 을 고려하여 메모리 상에서 실제 그 블럭이 차지하는 size를 의미합니다.

 

asize를 만들어주고, asize 만큼 비어있는 가용 블럭 (free block) 을 찾습니다. 적절한 크기의 가용 블럭 (free block) 을 찾지 못한 경우, extend_heap메소드를 이용해 힙의 크기를 max(asize, CHUNKSIZE) 만큼 증가시킨 후 증가시킨 공간에 place 메소드를 통해 memory allocate 를 수행합니다. extend_heap 메소드와 place 메소드은 다음과 같습니다.

 

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

    size = (words%2) ? (words+1) * WSIZE : words * WSIZE; // adjust size even align
    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)); // Set epilogue Block
    return coalesce(bp);
}

extend_heap 은 parameter words 사이즈만큼 힙 크기를 증가시키고, 가용 블럭의 주소를 리턴하는 함수입니다.

mem_sbrk 를 통해 힙 사이즈를 증가시키고, 증가시킨 힙 공간만큼 가용 블럭이 생겼으므로, header와 footer 에 가용 영역에 대한 정보를 mapping 하고 epilogue block 을 표시해줍니다. 그리고 coalesce 를 통해 연결할 가용 블럭이 있다면 가용 블럭을 extend 시켜줍니다. coalesce 함수는 다음과 같습니다.

 

static void *coalesce(void *bp){
    size_t prev_alloc = GET_ALLOC(FTRP(PREV_BLKP(bp))); // allocation status of previous block
    size_t next_alloc = GET_ALLOC(HDRP(NEXT_BLKP(bp))); // allocation status of next block
    size_t size =  GET_SIZE(HDRP(bp));

    if (prev_alloc && next_alloc){  // If two blocks are allocated already, return bp CASE 1
        return bp; 
    }
    else if (prev_alloc && !next_alloc){  // If next block is free block, return extended block CASE 2
        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){ // If previous block is free block, return extended block CASE 3
        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 { // If two blocks are free block, return extended block CASE 4
        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; 
}

Introduction to Malloc lab 에서 설명드렸던 coalesce 의 case 별로 구현해주었습니다.

 

다음은 place 메소드에 대한 설명입니다.

static void place(void *bp, size_t asize) {
    //쪼개기 미구현 함수
    /*
    PUT(HDRP(bp), PACK(asize, 1));
    PUT(FTRP(bp), PACK(asize, 1));
    */

    //쪼개기 구현
    size_t ThisBlockSize = GET_SIZE(HDRP(bp)); 
    if ( (ThisBlockSize-asize) >= (2*DSIZE)){ // 2*DSIZE 는 OVERHEAD와 최소payload 의 합과 같습니다.
        PUT(HDRP(bp), PACK(asize,1)); 
        PUT(FTRP(bp), PACK(asize,1)); 
        bp = NEXT_BLKP(bp);
        PUT(HDRP(bp), PACK(ThisBlockSize-asize,0));
        PUT(FTRP(bp), PACK(ThisBlockSize-asize,0)); 
    }
    else{
        PUT(HDRP(bp), PACK(ThisBlockSize,1));
        PUT(FTRP(bp), PACK(ThisBlockSize,1));
    }
};

쪼개기를 이용하지 않고, 그냥 항상 가용 블럭의 처음과 끝을 모두 사용할 경우, 실제 메모리의 크기보다 힙이 커지게 되어 Segmentation Faults 가 발생합니다. 쪼개기를 이용하여 place 를 구현하는 방법은 주석과 코드와 같이 현재 가용블럭의 크기 (ThisBlockSize) 에서 asize (할당할 블럭의 adjusted size) 를 뺀 값이 OVERHEAD 와 최소payload(2words=8bytes)보다 크거나 같으면, 쪼개기를 수행할 수 있습니다. 쪼개기를 쓸 수 없는 경우, 가용블럭에 그냥 블럭에 대한 정보를 header와 footer 에 mapping 해줍니다.

 

이와 같이 구현하고, calloc 과 realloc 은 naive 방식으로 구현했던 것을 그대로 가져다 사용하면 다음과 같은 실행결과를 얻을 수 있습니다.

first fit 의 퍼포먼스 점수

naive 방식의 score 가 66점이었던 것을 생각하면, First Fit 을 사용하는 Implicit List 방식은 성능이 좋지 않은 것을 알 수 있습니다. 이를 보완하기 위해서 Next fit 방식을 사용해보도록 하겠습니다.

 

Next fit 을 사용하기 위해서는 이전에 할당한 블록에 대한 포인터 주소 정보가 필요합니다. 이를 저장하기 위해서 새 변수 static char *previous_heap_listp 를 선언해주겠습니다.

 

그리고 find_fit 을 다음과 같이 구현해주도록 하겠습니다.

static void *find_fit (size_t asize) {
    void *bp;

    //Next Fit Code
    // use previous_heap_listp

    for (bp = previous_heap_listp; GET_SIZE(HDRP(bp)) > 0; bp = NEXT_BLKP(bp)) { // until meet Epilogue
        if ( (!GET_ALLOC(HDRP(bp))) && (asize <= GET_SIZE(HDRP(bp))) ) {
            previous_heap_listp = bp;
            return bp;
        }
    }

    void *bbp = previous_heap_listp;

    for (bp = heap_listp; bp < bbp; bp = NEXT_BLKP(bp)) { // until meet previous_heap_listp
        if ( (!GET_ALLOC(HDRP(bp))) && (asize <= GET_SIZE(HDRP(bp))) ) {
            previous_heap_listp = bp;
            return bp;
        }
    }

    return NULL;
}

먼저 이전에 사용한 블럭의 포인터를 이용하여 다음 fit block 을 찾다가 epilogue 를 만나기 전까지 찾지 못하면 다시 처음으로 돌아와 이전 사용한 블럭의 포인터를 만나기 전까지 fit block 을 찾습니다. 그럼에도 찾지 못한다면 NULL을 리턴합니다. 추가로, coalesce 시, 마지막으로 사용한 블럭의 포인터가 바뀔 수 있으므로 coalesce도 다음과 같이 수정해줍니다.

static void *coalesce(void *bp){
    size_t prev_alloc = GET_ALLOC(FTRP(PREV_BLKP(bp))); // allocation status of previous block
    size_t next_alloc = GET_ALLOC(HDRP(NEXT_BLKP(bp))); // allocation status of next block
    size_t size =  GET_SIZE(HDRP(bp));

    if (prev_alloc && next_alloc){  // If two blocks are allocated already, return bp CASE 1
        previous_heap_listp = bp; // for next fit
        return bp; 
    }
    else if (prev_alloc && !next_alloc){  // If next block is free block, return extended block CASE 2
        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){ // If previous block is free block, return extended block CASE 3
        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 { // If two blocks are free block, return extended block CASE 4
        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); 
    }

    previous_heap_listp = bp;  // for next fit
    return bp; 
}

Next Fit 을 통해 malloc free 를 구현했을 때 얻을 수 있는 점수는 다음과 같습니다.

Next fit 의 퍼포먼스 점수

 

더 나아가, place 를 다음과 같이 구현하면 utilization score 가 더 상승해 높은 점수를 얻을 수 있습니다.

남는 가용블럭의 사이즈가 0보다 크기만 하면 남겨두는 방식으로 구현하였는데, coalesce 시 사용하지 않는 free block 을 더 줄일 수 있어 utilization 점수가 상승하는 것 같습니다.

 

향상된 place 코드는 다음과 같습니다.

static void place(void *bp, size_t asize) {
    size_t currentBlockSize = GET_SIZE(HDRP(bp));
    PUT(HDRP(bp), PACK(asize,1));
    PUT(FTRP(bp), PACK(asize,1));

    size_t remainderBlockSize = currentBlockSize - asize;
    if (remainderBlockSize > 0) {
        PUT(HDRP(NEXT_BLKP(bp)), PACK(remainderBlockSize, 0));
        PUT(FTRP(NEXT_BLKP(bp)), PACK(remainderBlockSize, 0));
    }
}

향상된 place 를 구현한 퍼포먼스 점수