[Malloc Lab] LIFO 방식의 Explicit List (명시적 리스트)

이번에는 Explicit List 방식으로 malloc / free 를 구현해보도록 하겠습니다. Introduction 에서 다뤘던 Explicit List 의 개념을 상기해보며 접근해봅시다.

 

Explicit List 방식으로 다룰 때 가장 핵심은 Free Block 을 관리하는 Doubled Linked List 가 있다고 생각하는 것입니다.

 

Doubled Linked List 형태의 Free Block 관리

Free Block 중 가장 첫번째 가용 블럭은 prev로 NULL 을 가리키고 succ으로는 다음 free block 을 가리킵니다. 그리고 마지막 블럭의 succ 은 NULL을 가리킵니다.

 

*prev = previous, succ = succeeding

 

그리고 LIFO 방식으로 가용블럭을 manage 할 것을 기억하며 가용블럭을 사용할 때는 가장 첫번째 free block을 사용하고, free 를 통해 가용블럭을 추가할 때는 첫번째 block 이 되도록 해주어야합니다.

 

따라서 다음과 같은 메소드들을 정의해주었습니다.

 

*GET_PTR 는 매크로 함수로 prev, succ 에 저장한 이전 블럭, 다음 블럭의 주소를 char * 형태로 반환합니다.

#define GET_PTR(bp) ((char *)(GET(bp))

 

static void add_free_list(void *bp) {
    if (first_block_pointer = NULL) {
        first_block_pointer = bp;
    } else {
        PUT(SUCC(bp), first_block_pointer);
        PUT(PRED(bp), NULL);
        first_block_pointer = bp;
    }
}

static void delete_from_free_list(void *bp) {
    if (!GET_P(PRED(bp))) { // 삭제하고자 하는 free block 이 첫번째 free node라면.
        if (!GET_P(SUCC(bp))) { // 삭제하고자 하는 free block 이 유일한 free block 이라면.
            first_block_pointer = NULL;
            return;
        } else {
            PUT(PRED(GET_P(SUCC(bp))), NULL); // 2번째 free block을 1번 free block으로 만들어 줌.
            first_block_pointer = GET_P(SUCC(bp));
        }
    } else { // 삭제하고자 하는 free block 이 첫번째 free node 가 아니라면
        PUT(SUCC(GET_P(PRED(bp))), GET_P(SUCC(bp)));
        PUT(PRED(GET_P(SUCC(bp))), GET_P(PRED(bp)));
    }
}

 

이 메소드들을 이용하면, free block 을 LIFO 방식의 Explicit List 로 Handling 할 수 있습니다.

 

이를 이용해 place, extend_heap, coalesce, free 도 적절하게 수정해줍니다.

 

place 함수만 부연 설명을 하자면, 사용할 가용블럭은 delete_from_free_list 메소드로 가용블럭 리스트에서 제거한 후 payload 할당 후 남은 block 은 add_free_list로 다시 가용블럭 리스트에 enroll 해줍니다.

 

다음 코드는 다음과 같습니다.

 

static void place(void *bp, size_t asize) {
    //쪼개기 구현
    size_t ThisBlockSize = GET_SIZE(HDRP(bp)); 
    delete_from_free_list(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));
        add_free_list(bp);
    }
    else {
        PUT(HDRP(bp), PACK(ThisBlockSize,1));
        PUT(FTRP(bp), PACK(ThisBlockSize,1));
    }
}

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;
        return bp; 
    }
    else if (prev_alloc && !next_alloc){  // If next block is free block, return extended block CASE 2
        delete_from_free_list(bp);
        size += GET_SIZE(HDRP(NEXT_BLKP(bp))); 
        PUT(HDRP(bp),PACK(size,0)); 
        PUT(FTRP(bp), PACK(size,0)); 
        add_free_list(bp);
    }
    else if(!prev_alloc && next_alloc){ // If previous block is free block, return extended block CASE 3
        delete_from_free_list(bp);
        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);
        add_free_list(bp);
    }
    else { // If two blocks are free block, return extended block CASE 4
        delete_from_free_list(bp);
        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); 
        add_free_list(bp);
    }

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

static void *extend_heap(size_t words) {
    void *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
    PUT(PRED(bp), NULL);
    PUT(SUCC(bp), NULL);
    add_free_list(bp);
    return coalesce(bp);
}

void free (void *ptr) {
    if(!ptr) {
        return;
    }

    size_t size = GET_SIZE(HDRP(ptr));
    PUT(HDRP(ptr), PACK(size, 0));
    PUT(FTRP(ptr), PACK(size, 0));
    PUT(PRED(ptr), NULL);
    PUT(SUCC(ptr), NULL);
    add_free_list(ptr);
    coalesce(ptr);
}

 

마지막으로 explicit list 의 특성을 이용하여 find_fit 도 수정해주면 완성입니다!

 

static void *find_fit (size_t asize) {
    void *bp;
    
    for (bp = first_block_pointer; bp != NULL; bp = GET_P(SUCC(bp))) { // until meet Epilogue
        if ( (!GET_ALLOC(HDRP(bp))) && (asize <= GET_SIZE(HDRP(bp))) ) {
            return bp;
        }
    } 
    return NULL;
}

 

최종 소스코드는 다음과 같습니다.

#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>

#include "mm.h"
#include "memlib.h"

/* If you want debugging output, use the following macro.  When you hand
 * in, remove the #define DEBUG line. */
#define DEBUG
#ifdef DEBUG
# define dbg_printf(...) printf(__VA_ARGS__)
#else
# define dbg_printf(...)
#endif


/* do not change the following! */
#ifdef DRIVER
/* create aliases for driver tests */
#define malloc mm_malloc
#define free mm_free
#define realloc mm_realloc
#define calloc mm_calloc
#endif /* def DRIVER */

#define WSIZE 4
#define DSIZE 8
#define CHUNKSIZE (1 << 12)
#define OVERHEAD 8
#define MAX(x, y) ((x) > (y) ? (x) : (y)) 
#define PACK(size, alloc) ((size) | (alloc)) 
#define GET(p) (*(unsigned int *)(p)) // unsigned int 반환
#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 PRED(bp) ((char *)(bp))
#define SUCC(bp) ((char *)(bp) + WSIZE)
#define GET_PTR(bp) ((char *)GET(bp))

/* single word (4) or double word (8) alignment */
#define ALIGNMENT 8

/* rounds up to the nearest multiple of ALIGNMENT */
#define ALIGN(p) (((size_t)(p) + (ALIGNMENT-1)) & ~0x7)

/*copy from naive.c*/
#define SIZE_T_SIZE (ALIGN(sizeof(size_t)))
#define SIZE_PTR(p)  ((size_t*)(((char*)(p)) - SIZE_T_SIZE))

static void place(void *bp, size_t asize);
static void *coalesce(void *bp);;
static void *find_fit (size_t asize);
static void *extend_heap(size_t words);
static void add_free_list(void *bp);
static void delete_from_free_list(void *bp);

static char *heap_listp = 0; // pointer of first block
static char *previous_heap_listp = 0;
static char *first_block_pointer = NULL;


// Root Node 는 NULL, Tail Node 도 NULL.

static void add_free_list(void *bp) {
    if (first_block_pointer = NULL) {
        first_block_pointer = bp;
    } else {
        PUT(SUCC(bp), first_block_pointer);
        PUT(PRED(bp), NULL);
        first_block_pointer = bp;
    }
}

static void delete_from_free_list(void *bp) {
    if (!GET_PTR(PRED(bp))) { // 삭제하고자 하는 free block 이 첫번째 free node라면.
        if (!GET_PTR(SUCC(bp))) { // 삭제하고자 하는 free block 이 유일한 free block 이라면.
            first_block_pointer = NULL;
            return;
        } else {
            PUT(PRED(GET_PTR(SUCC(bp))), NULL); // 2번째 free block을 1번 free block으로 만들어 줌.
            first_block_pointer = GET_PTR(SUCC(bp));
        }
    } else { // 삭제하고자 하는 free block 이 첫번째 free node 가 아니라면
        PUT(SUCC(GET_PTR(PRED(bp))), GET_PTR(SUCC(bp)));
        PUT(PRED(GET_PTR(SUCC(bp))), GET_PTR(PRED(bp)));
    }
}

static void place(void *bp, size_t asize) {
    //쪼개기 구현
    size_t ThisBlockSize = GET_SIZE(HDRP(bp)); 
    delete_from_free_list(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));
        add_free_list(bp);
    }
    else {
        PUT(HDRP(bp), PACK(ThisBlockSize,1));
        PUT(FTRP(bp), PACK(ThisBlockSize,1));
    }
};

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;
        return bp; 
    }
    else if (prev_alloc && !next_alloc){  // If next block is free block, return extended block CASE 2
        delete_from_free_list(bp);
        size += GET_SIZE(HDRP(NEXT_BLKP(bp))); 
        PUT(HDRP(bp),PACK(size,0)); 
        PUT(FTRP(bp), PACK(size,0)); 
        add_free_list(bp);
    }
    else if(!prev_alloc && next_alloc){ // If previous block is free block, return extended block CASE 3
        delete_from_free_list(bp);
        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);
        add_free_list(bp);
    }
    else { // If two blocks are free block, return extended block CASE 4
        delete_from_free_list(bp);
        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); 
        add_free_list(bp);
    }

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

static void *extend_heap(size_t words) {
    void *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
    PUT(PRED(bp), NULL);
    PUT(SUCC(bp), NULL);
    add_free_list(bp);
    return coalesce(bp);
}

/*
 * 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 를 prologue footer block 에 locate.
    previous_heap_listp = heap_listp; // 첫번째 extend_heap 후 가장 먼저 나타나는 가용블럭 포인터

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

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

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

    // Using Explicit List
    for (bp = first_block_pointer; bp != NULL; bp = GET_PTR(SUCC(bp))) { // until meet Epilogue
        if ( (!GET_ALLOC(HDRP(bp))) && (asize <= GET_SIZE(HDRP(bp))) ) {
            return bp;
        }
    } 
    return NULL;

    // Next Fit
    // for (bp = previous_heap_listp; GET_SIZE(HDRP(bp)) > 0; bp = NEXT_BLKP(bp)) { // until meet Epilogue
    //     // printf("%x\n", bp);
    //     if ( (!GET_ALLOC(HDRP(bp))) && (asize <= GET_SIZE(HDRP(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))) ) {
    //         return bp;
    //     }
    // }

    // return NULL;
}

/*
 * 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 );
    // }
    asize = ALIGN(size + OVERHEAD);

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

/*
 * free
*/
void free (void *ptr) {
    if(!ptr) {
        return;
    }

    size_t size = GET_SIZE(HDRP(ptr));
    PUT(HDRP(ptr), PACK(size, 0));
    PUT(FTRP(ptr), PACK(size, 0));
    PUT(PRED(ptr), NULL);
    PUT(SUCC(ptr), NULL);
    add_free_list(ptr);
    coalesce(ptr);
}

/*
 * realloc - you may want to look at mm-naive.c
 */
void *realloc(void *oldptr, size_t size) {
    size_t oldsize;
    void *newptr;

    /* If size == 0 then this is just free, and we return NULL. */
    if(size == 0) {
        free(oldptr);
        return 0;
    }

    /* If oldptr is NULL, then this is just malloc. */
    if(oldptr == NULL) {
        return malloc(size);
    }

    newptr = malloc(size);

    /* If realloc() fails the original block is left untouched  */
    if(!newptr) {
        return 0;
    }

    /* Copy the old data. */
    oldsize = *SIZE_PTR(oldptr);
    if(size < oldsize) oldsize = size;
        memcpy(newptr, oldptr, oldsize);

    /* Free the old block. */
    free(oldptr);

    return newptr;
}

/*
 * calloc - you may want to look at mm-naive.c
 * This function is not tested by mdriver, but it is
 * needed to run the traces.
 */
void *calloc (size_t nmemb, size_t size) {
    size_t bytes = nmemb * size;
    void *newptr;

    newptr = malloc(bytes);
    memset(newptr, 0, bytes);

    return newptr;
}


/*
 * Return whether the pointer is in the heap.
 * May be useful for debugging.
 */
static int in_heap(const void *p) {
    return p < mem_heap_hi() && p >= mem_heap_lo();
}

/*
 * Return whether the pointer is aligned.
 * May be useful for debugging.
 */
static int aligned(const void *p) {
    return (size_t)ALIGN(p) == (size_t)p;
}

/*
 * mm_checkheap
 */
void mm_checkheap(int verbose) {
}

 

Explicit List 구현 결과는 다음과 같습니다.

 

Explicit 구현 결과