[시스템 프로그래밍] Malloc Lab Explicit (2)

 

 

 

7. free 함수 구현

 

 

할당된 메모리를 가용 가능한 상태로 만드는 free 함수를 구현하자.

 

 

 

 

free 함수는 반환할 블록의 위치를 인자로 받고 해당 블록의 가용 상태로 바꾸는 역할을 한다.

 

 

이제 다시 테스트를 돌려 보자.

 

 

 

 

 

 

 

성능에 변화가 없다 -_-

 

아마도 free로 블록을 가용 상태로 만들었지만 coalescing 작업을 수행하지 않아 가용 리스트에 free 된 블록이 들어가지 않아 아무 효과를 얻지 못하는 것 같다.

 

 

 

8. place 함수 수정 + free 함수 수정

 

 

 

 

 

free 함수에 coalesce 작업을 추가해 가용 리스트에 가용 블록을 넣어 주자.

 

implicit에서 작성한 것처럼 place 함수를 수행할 때 블록을 나눌 수 있는 경우 나눠서 공간을 확보하자.

 

 

 

 

 

 

implicit 때와 다르게 가용 리스트에서 블록을 제거하는 부분이 추가됐다.

 

공간이 넉넉한 경우 블록을 할당하고 분할 작업까지 함께 수행한다.

남는 공간을 가용 공간으로 설정한 후 coalesce 함수를 호출해 가용 리스트에 넣어준다.

 

공간이 남지 않으면 이전에 작성한 로직대로 동작하도록 하자.

 

 

 

다시 테스트 해 보자.

 

 

 

 

 

 

성능이 많이 향상됐음을 확인할 수 있다.

 

 

 

explicit 방식 외에도 부분 가용 리스트를 사용하거나 트리 구조를 사용하면 성능을 더 끌어올릴 수 있다.

실제 C에서는 malloc을 구현 할 때 트리 자료구조를 사용해서 구현하기도 했다.

 

 

<전체 소스코드>

 

#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 */

/* single word (4) or double word (8) alignment */

/* rounds up to the nearest multiple of ALIGNMENT */

/*
 * Initialize: return -1 on error, 0 on success.
 */

#define ALIGNMENT 8

#define HDRSIZE 4
#define FTRSIZE 4
#define WSIZE 4
#define DSIZE 8
#define CHUNKSIZE (1<<12)
#define OVERHEAD 8
#define MINSPACE 24

#define MAX(x, y) ((x) > (y) ? (x) : (y))
#define MIN(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 GET8(p) (*(unsigned long *)(p))
#define PUT8(p, val) (*(unsigned long *)(p) = (unsigned long)(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_FREEP(bp) (*(char**)(bp + DSIZE))
#define PREV_FREEP(bp) (*(char**)(bp))        

#define NEXT_FREE_BLKP(bp) ((char*)GET8((char*)(bp)))
#define PREV_FREE_BLKP(bp) ((char*)GET8((char*)(bp) + DSIZE))

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

#define ALIGN(p) (((size_t)(p) + (ALIGNMENT-1)) & ~0x7)

static char* heap_listp = 0;
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 void remove_block(void* bp);

static char* free_listp;

int mm_init(void) {

    if((heap_listp = mem_sbrk(DSIZE + 4 * HDRSIZE)) == NULL) return -1;    

    PUT(heap_listp, 0); // padding
    PUT(heap_listp + WSIZE, PACK(MINSPACE, 1)); // header
    PUT(heap_listp + DSIZE, 0); // prev
    PUT(heap_listp + DSIZE + WSIZE, 0); // next
    PUT(heap_listp + MINSPACE, PACK(MINSPACE, 1)); // footer
    PUT(heap_listp + WSIZE + MINSPACE, PACK(0, 1)); // set epilogue
    
    free_listp = heap_listp + DSIZE; // set list 

    if(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; // resize for align

    if(size < MINSPACE) size = MINSPACE; // set min size

    if((long)(bp = mem_sbrk(size)) == -1) return NULL;

    PUT(HDRP(bp), PACK(size, 0)); // set header (not prologue)
    PUT(FTRP(bp), PACK(size, 0)); // set footer (not prologue)
    PUT(HDRP(NEXT_BLKP(bp)), PACK(0, 1)); // set epilogue
    
    return coalesce(bp);
}

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

    for(bp = free_listp; GET_ALLOC(HDRP(bp)) == 0; bp = NEXT_FREEP(bp)) {
        if(asize <= (size_t)GET_SIZE(HDRP(bp))) return bp;
    } // start with list's first potion

    return NULL;
}

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

    if((csize - asize) >= MINSPACE) {
        PUT(HDRP(bp), PACK(asize, 1));
        PUT(FTRP(bp), PACK(asize, 1));
        
        remove_block(bp);

        bp = NEXT_BLKP(bp);
        PUT(HDRP(bp), PACK(csize - asize, 0));
        PUT(FTRP(bp), PACK(csize - asize, 0));
        coalesce(bp);
    } else {
        PUT(HDRP(bp), PACK(csize, 1)); // set aligned area
        PUT(FTRP(bp), PACK(csize, 1));
        remove_block(bp); // remove from liste
    }

    
}

static void remove_block(void *bp) {
    // control linked list

    if(PREV_FREEP(bp)) NEXT_FREEP(PREV_FREEP(bp)) = NEXT_FREEP(bp);
    else free_listp = NEXT_FREEP(bp);

    PREV_FREEP(NEXT_FREEP(bp)) = PREV_FREEP(bp);    
}

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

    if(size <= 0) return NULL; // edge case
    asize = MAX(ALIGN(size) + DSIZE, MINSPACE); // set min val (24)

    if((bp = find_fit(asize))) { // find memory block
        place(bp, asize);
        return bp;
    }

    extendsize = MAX(asize, CHUNKSIZE); // can't find. need to extend
    if((bp = extend_heap(extendsize / WSIZE)) == NULL) return NULL;

    place(bp, asize);

    return bp;
}

/*
 * 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));
    
    coalesce(ptr);
}

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

    size_t asize = MAX(ALIGN(size) + DSIZE, MINSPACE);
    
    if(size <= 0) { // edge case 1
        free(oldptr);
        return 0;
    }    

    if(oldptr == NULL) return malloc(size); // edge case 2

    size_t oldsize = GET_SIZE(HDRP(oldptr)); 
    if(asize == oldsize) return oldptr; // edge case 3

    if(asize <= oldsize) { // have to shorten
        size = asize;

        if(oldsize - size <= MINSPACE) return oldptr; // set min val (24)

        PUT(HDRP(oldptr), PACK(size, 1)); // new block with new size
        PUT(FTRP(oldptr), PACK(size, 1)); 
        PUT(HDRP(NEXT_BLKP(oldptr)), PACK(oldsize - size, 1));
        free(NEXT_BLKP(oldptr)); // free old block

        return oldptr;
    }

    void *newp = malloc(size); // re malloc
    if(newp == NULL) return 0;

    if(size < oldsize) oldsize = size;
    
    memcpy(newp, oldptr, oldsize); // copy memory
    free(oldptr);

    return newp;
}

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

    /* if prev and next all allocated, just insert block at the first of list */

    if(prev_alloc && !next_alloc) { // next is free, prev is allocated
        size += GET_SIZE(HDRP(NEXT_BLKP(bp))); // combine with next block

        remove_block(NEXT_BLKP(bp)); // remove from list

        PUT(HDRP(bp), PACK(size, 0)); // set header
        PUT(FTRP(bp), PACK(size, 0)); // set footer

    } else if(!prev_alloc && next_alloc) { // next is allocated, prev is free
        size += GET_SIZE(HDRP(PREV_BLKP(bp)));
        
        bp = PREV_BLKP(bp);
        remove_block(bp);

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

    } else if(!prev_alloc && !next_alloc) { // next and prev all free
        size += GET_SIZE(HDRP(PREV_BLKP(bp))) + GET_SIZE(HDRP(NEXT_BLKP(bp)));
        
        remove_block(PREV_BLKP(bp));
        remove_block(NEXT_BLKP(bp));
        bp = PREV_BLKP(bp);

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

    /* insert bp at the first of list */
    NEXT_FREEP(bp) = free_listp;
    PREV_FREEP(free_listp) = bp;
    PREV_FREEP(bp) = NULL;
    free_listp = bp;

    return bp;
}
/*
 * 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) {
    return NULL;
}


/*
 * 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) {
}